问题描述 链接到标题
给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。
你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j
，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次数。
示例 1：
输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
示例 2：
输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。
提示：
1 <= s.length <= 10⁵s[i]要么是'a'要么是'b'。
解题思路 链接到标题
枚举分割线 链接到标题
分割线从0枚举到n(数字表示分割线左侧有多少个字符)，删除分割线左侧的’b’和右侧的’a’，删除次数的最小值即为答案。
动态规划 链接到标题
考虑cnt[i]为前i个字符中’b’的数量，dp[i]为使前i个字符平衡的最小操作数：
- 当
s[i - 1] == 'a'时，cnt[i] = cnt[i - 1]，为了让前i个字符平衡，要么将这个’a’删掉，此时dp[i] = dp[i - 1] + 1，要么直接将前i个字符的的’b’全都删掉，此时dp[i] = cnt[i]；因此有dp[i] = min(dp[i - 1] + 1, cnt[i])； - 当
s[i - 1] == 'b'时，cnt[i] = cnt[i - 1] + 1，dp[i] = dp[i - 1]；
代码 链接到标题
枚举分割线 链接到标题
class Solution {
public:
int minimumDeletions(string s) {
// 两种选择，删掉不符合条件的'a'和删掉不符合条件的'b'
// cnt[i][0]表示前i个字符中'a'的数目
vector<vector<int>> cnt(s.size() + 1, vector<int>(2, 0));
for (int i = 1; i <= s.size(); ++i) {
if (s[i - 1] == 'a') {
cnt[i][0] = cnt[i - 1][0] + 1;
cnt[i][1] = cnt[i - 1][1];
} else {
cnt[i][0] = cnt[i - 1][0];
cnt[i][1] = cnt[i - 1][1] + 1;
}
}
int res = s.size();
for (int i = 0; i <= s.size(); ++i) {
res = std::min(res, i - cnt[i][0] + cnt[s.size()][0] - cnt[i][0]); // 枚举分割线，分割线左侧的'b'全删掉，分割线右侧的'a'全删掉
}
return res;
}
};
动态规划 链接到标题
class Solution {
public:
int minimumDeletions(string s) {
int n = s.size();
vector<int> dp(n + 1, 0);
vector<int> cnt(n + 1, 0); // 前n个字符中'b'的数目
for (int i = 1; i <= n; ++i) {
if (s[i - 1] == 'b') {
cnt[i] = cnt[i - 1] + 1;
dp[i] = dp[i - 1];
} else {
cnt[i] = cnt[i - 1];
dp[i] = std::min(dp[i - 1] + 1, cnt[i]);
}
}
return dp[n];
}
};