精通网站开发书籍,做网站获取手机号码,金华市住房建设局网站,要维护公司的网站该怎么做LeetCode 1653. 使字符串平衡的最少删除次数
难度#xff1a;middle\color{orange}{middle}middle
Rating#xff1a;1794\color{orange}{1794}1794 题目描述
给你一个字符串 sss #xff0c;它仅包含字符 ′a′a′a′ 和 ′b′b′b′ 。
你可以删除 sss 中任意…LeetCode 1653. 使字符串平衡的最少删除次数
难度middle\color{orange}{middle}middle
Rating1794\color{orange}{1794}1794 题目描述
给你一个字符串 sss 它仅包含字符 ′a′a′a′ 和 ′b′b′b′ 。
你可以删除 sss 中任意数目的字符使得 sss 平衡 。当不存在下标对 (i,j)(i,j)(i,j) 满足 iji jij 且 s[i]′b′s[i] bs[i]′b′ 的同时 s[j]′a′s[j] as[j]′a′ 此时认为 sss 是 平衡 的。
请你返回使 sss 平衡 的 最少 删除次数。
示例 1
输入s aababbab
输出2
解释你可以选择以下任意一种方案
下标从 0 开始删除第 2 和第 6 个字符aababbab - aaabbb
下标从 0 开始删除第 3 和第 6 个字符aababbab - aabbbb。示例 2
输入s bbaaaaabb
输出2
解释唯一的最优解是删除最前面两个字符。提示
1s.length1051 s.length 10^{5}1s.length105s[i]s[i]s[i] 要么是 ′a′a′a′ 要么是 ′b′b′b′ 。 算法
(枚举)
通过删除部分字符串使得字符串达到下列三种情况之一即为平衡状态
字符串全为 “a”字符串全为 “b”字符串既有 “a” 也有 “b”且所有 “a” 都在所有 “b” 左侧。
为了达到第 1 种情况最少需要删除所有的 “b”。
为了达到第 2 种情况最少需要删除所有的 “a”。
而第 3 种情况可以在原字符串相邻的两个字符之间划一条间隔删除间隔左侧所有的 “b” 和间隔右侧所有的 “a” 即可达到。用 leftb 表示间隔左侧的 “b” 的数目righta 表示间隔左侧的 “a” 的数目leftbrighta 即为当前划分的间隔下最少需要删除的字符数。这样的间隔一共有 n−1 种其中 n 是 s 的长度。遍历字符串 s即可以遍历 n−1 种间隔同时更新 leftb 和 righta 的数目。而上文讨论的前两种情况其实就是间隔位于首字符前和末字符后的两种特殊情况可以加入第 3 种情况一并计算。
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是链表的长度。需要遍历链表一次 空间复杂度 : O(1)O(1)O(1)
C 代码
class Solution {
public:int minimumDeletions(string s) {int righta 0;for (int i 0; i s.size(); i ) {if (s[i] a) righta ;}int res righta;int leftb 0;for (int i 0; i s.size(); i ) {if (s[i] a)righta --;else leftb ;res min(res, leftb righta);}return res;}
};
