LeetCode - 1653 使字符串平衡的最少删除次数
创始人
2024-05-29 16:19:10
0次

目录

题目来源

题目描述

示例

提示

题目解析

算法源码


题目来源

1653. 使字符串平衡的最少删除次数 - 力扣(LeetCode)

题目描述

给你一个字符串 s ,它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符,使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ,且 s[i] = 'b' 的同时 s[j]= 'a' ,此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例

输入:s = "aababbab"
输出:2
解释:你可以选择以下任意一种方案:
下标从 0 开始,删除第 2 和第 6 个字符("aababbab" -> "aaabbb"),
下标从 0 开始,删除第 3 和第 6 个字符("aababbab" -> "aabbbb")。

输入:s = "bbaaaaabb"
输出:2
解释:唯一的最优解是删除最前面两个字符。

提示

  • 1 <= s.length <= 105
  • s[i] 要么是 'a' 要么是 'b'​ 。

题目解析

本题最优思路是采用动态规划。

我们可以定义一个dp数组,dp[i]的含义是将输入字符串s的0~i区间变得平衡的最少修改次数,而dp[i+1]其实就是相当于在dp[i]的0~i区间尾部追加一个字符,此时我们只需要考虑追加字符的处理来保持0~i+1区间平衡即可。

如果追加的s[i] == ‘b’, 则不会破坏平衡。

如果追加的s[i] == 'a',则会破坏破坏,此时有两种删除策略:

  1. 由于0~i-1已经平衡了,因此我们可以删除s[i],已期不会破坏0~i-1已形成的平衡,即dp[i] = dp[i-1] + 1  (+1对应删除s[i]的动作)
  2. 如果我们不删除s[i]的话,则需要将 0~i-1 中所有的b删除,因此在遍历s的过程中,我们还需要记录 0 ~ i 范围内的b的数量,比如countB[i] 含义为 0~i范围内b的数量。此时 dp[i] = countB[i-1]

我们只需要取上面两个dp[i]中最小的即可,即dp[i] = min(dp[i-1] + 1, countB[i-1])

但是上面将dp,countB定义为数组非常浪费内存,这里起始最终只要求的是输入s字符串0~n-1区间变得平衡的最小次数,因此我们不需要缓存其他区间最小数次数据,而是可以对dp,countB数组进行压缩,每次用最新值覆盖前一个值即可。

算法源码

JS

/*** @param {string} s* @return {number}*/
var minimumDeletions = function(s) {let dp = 0 // dp记录的是将s的[0, i]区间变得平衡的最少次数let countB = 0 // countB 记录的是 s 的 [0, i]区间中b字符的个数for(let i = 0; i < s.length; i++) {if(s[i] == 'a') dp = Math.min(dp + 1, countB) // 末尾新增a会破坏平衡,此时需要进行删除动作else countB++ // 末尾新增b不会破坏平衡}return dp;
};

 

 

Java

class Solution {public int minimumDeletions(String s) {int dp = 0; // dp记录的是将s的[0, i]区间变得平衡的最少次数int countB = 0; // countB 记录的是 s 的 [0, i]区间中b字符的个数for(int i=0; i < s.length(); i++) {if(s.charAt(i) == 'a') dp = Math.min(dp + 1, countB); // 末尾新增a会破坏平衡,此时需要进行删除动作else countB++; // 末尾新增b不会破坏平衡}return dp;}
}

 

Python

class Solution(object):def minimumDeletions(self, s):dp = 0  # dp记录的是将s的[0, i]区间变得平衡的最少次数countB = 0  # countB 记录的是 s 的 [0, i]区间中b字符的个数for c in s:if c == 'a':dp = min(dp + 1, countB)  # 末尾新增a会破坏平衡,此时需要进行删除动作else:countB += 1  # 末尾新增b不会破坏平衡return dp

相关内容

热门资讯

普京:难怪您会选这里作为APE... 为期两天的亚太经合组织工商领导人峰会在深圳举行。俄罗斯总统普京在18日的峰会上发表致辞。普京表示,深...
猪价重回9元关口 养殖仍面临亏... 11月17日早上,28个重点监测地区瘦肉型标猪出栏均价为9.12元/公斤,比前一天上涨了一毛钱。尽管...
温泉直播拍顾客还拉黑质疑者 隐... 近日,有网友发帖称,上海汤连得温泉的直播间镜头长期对准洗浴区通往三楼休息区的楼梯通道。这里是顾客上下...
湖北老虎墩墓地出土漆立人凤形勺... 11月18日上午,国家文物局召开“考古中国”重大项目重要进展工作会,发布四项考古最新进展。其中,湖北...
小米回应“雷军深圳发言紧张” ... 在深圳举办的2026年APEC工商领导人峰会上,雷军分享了他对AI现状的看法。他认为技术变化迅速,但...
为何都说“APEC需要中国” ... 2026年APEC工商领导人峰会在深圳举行,吸引了21个经济体的两千多位工商界代表。峰会首日议程紧凑...
黄金会跌回400元一克吗?专家... 黄金会跌回400元一克吗?专家预测不乐观!黄金价格在2024年大幅上涨后,许多人关心2025年的走势...
东风61列装释放战略信号引发岛... 东风-61洲际导弹近日正式列装火箭军,这一消息引发了台湾岛内媒体的广泛关注。据央视网《海峡两岸》节目...
也门首都萨那传出巨大爆炸声 多... 据总台报道员消息,当地时间17日,也门首都萨那传出巨大爆炸声。另据也门胡塞武装消息,沙特阿拉伯主导的...
潮汕牛肉丸圈粉无数中外媒体记者... 潮汕牛肉丸圈粉无数中外媒体记者。11月13日,在APEC会议周新闻中心,浓郁的岭南烟火气在镜头与键盘...
哈啰单车新车型被吐槽“单车刺客... 近日,有网友在北京一路口扫到一辆蓝色新款哈啰单车,页面显示骑行30分钟收费15元,价格远高于普通共享...
女子蹲金价1年不到3万拿下32... “低价加工黄金,只要30元!”近日,在浙江湖州长兴的乡间小路上,这声吆喝吸引了村民刘大妈的注意。远低...
女子腿被压车轮下旁边女子竟指挥... 11月16日(发布),一段网友发布的视频引发热议。视频中,一名女子腿部被压在车轮下,趴在地上痛苦不已...
油价或再下调 今日价格 新一轮... 油价或再下调 今日价格 新一轮调价窗口将启。11月首调油价大跌后,新一轮油价调整有望继续下降。调整窗...
医生建议最近穿袜子睡觉:入睡快... 最近降温,每天晚上钻进被窝就像钻进“冰窖”——躺了半天双脚还是凉的。很多人觉得忍忍就好了,或等睡着就...
陆毅女儿宣布出道,“爸爸去哪儿... 继黄磊女儿10月时尚活动完成“内娱首秀”、郭涛儿子11月入选电影频道2026“星辰大海”青年演员优选...
14岁男孩带内耗妈妈运动治好内... 近日,山东菏泽。一段孩子陪妈妈运动,并喊着:“内耗的妈妈养不出明媚的孩子”的视频火了。记者联系上视频...
新娘强忍泪水与兄弟姐妹吃“分家... 广东汕尾。按照当地习俗,婚礼上新娘与兄弟姐妹吃“分家饭”,新娘强忍泪水,弟弟崩溃大哭,妹妹不敢直视姐...
消防员被困电梯名场面 网友:主... 近日,成都消防开展工作室意外被困电梯于是求救,赶来救援的同行忍不住现场“无情嘲笑”。网友:主打一个自...
男子结婚8年给妻子买10柜子衣... 11月17日(发布),河南长葛的石金龙和妻子罗玉娇结婚8年,最爱给妻子买衣服,“她身材好,穿着好看,...