class Solution {
public:
int minimumDeletions(string s) {
}
};
1653. 使字符串平衡的最少删除次数
给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。
你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。
请你返回使 s 平衡 的 最少 删除次数。
示例 1：
输入：s = "aababbab" 输出：2 解释：你可以选择以下任意一种方案： 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"）， 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
示例 2：
输入：s = "bbaaaaabb" 输出：2 解释：唯一的最优解是删除最前面两个字符。
提示：
1 <= s.length <= 105s[i] 要么是 'a' 要么是 'b' 。原站题解
python3 解法, 执行用时: 636 ms, 内存消耗: 18.4 MB, 提交时间: 2022-12-11 13:02:33
class Solution:
def minimumDeletions(self, s: str) -> int:
n = len(s)
dp = [0 for _ in range(n + 1)]
b = 0
for i, c in enumerate(s):
if c == 'b':
dp[i+1] = dp[i]
b += 1
elif c == 'a':
dp[i+1] = min(dp[i] + 1, b) #删掉这个a，或者删除前面的所有b
return dp[n]
javascript 解法, 执行用时: 192 ms, 内存消耗: 50.9 MB, 提交时间: 2022-12-11 13:01:53
/**
* @param {string} s
* @return {number}
*/
/**
* @param {string} s
* @return {number}
*/
var minimumDeletions = function(s) {
const sList = s.split('')
const n = sList.length
let aCount = sList.reduce((sum,item)=> item === 'a' ? sum + 1 : sum,0)
let bCount = 0
let result = aCount
sList.forEach(v=>{
if(v === 'a') aCount --
else bCount++
result = Math.min(result, aCount + bCount)
})
return result
};
python3 解法, 执行用时: 1072 ms, 内存消耗: 18.5 MB, 提交时间: 2022-12-11 13:01:33
class Solution:
def minimumDeletions(self, s: str) -> int:
n = len(s)
count = [0] * (n + 1)
for i,c in enumerate(s):
if c == 'a':
count[i+1] = count[i] + 1
else:
count[i+1] = count[i]
ans = float("inf")
for i in range(n):
# 到i有多少个'b'，后面有多少个'a'
b = i - count[i]
a = count[-1] - count[i+1]
if not a and not b:
return 0
ans = min(ans, b+a)
return ans
python3 解法, 执行用时: 336 ms, 内存消耗: 15.6 MB, 提交时间: 2022-12-11 13:01:23
class Solution:
def minimumDeletions(self, s: str) -> int:
# b的个数
cnt = ans = 0
for c in s:
if c == 'b':
# 'b'为结尾，必然不影响之前的平衡性
cnt += 1
else:
# 'a'为结尾，要么是上一个的平衡结果再删掉这个'a',要么要删光前面的'b'
ans = min(ans + 1, cnt)
return ans
cpp 解法, 执行用时: 84 ms, 内存消耗: 35.8 MB, 提交时间: 2022-12-11 13:00:53
class Solution {
public:
int minimumDeletions(string s) {
int n=s.size(),cnt_b=0;
vector<int> dp(n+1,0);
for(int i=0;i<n;++i){
if(s[i]=='b'){
dp[i+1]=dp[i];
++cnt_b;
} else {
dp[i+1]=min(dp[i]+1, cnt_b);
}
}
return dp[n];
}
};
cpp 解法, 执行用时: 84 ms, 内存消耗: 21.9 MB, 提交时间: 2022-12-11 13:00:06
// 对整个字符串进行遍历，当碰到'b'时入栈，当碰到'a'时，若栈非空，则进行计数，同时pop掉一个栈顶元素
class Solution {
public:
int minimumDeletions(string s) {
stack<char> char_stack;
int cnt=0;
for(int i=0;i<s.length();i++)
{
if(s[i]=='b')
char_stack.push(s[i]);
else
{
if(!char_stack.empty())
{
cnt++;
char_stack.pop();
}
}
}
return cnt;
}
};