目标
给你一个字符串 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^5
- s[i] 要么是 'a' 要么是 'b' 。
思路
有一个仅包含 a, b 两个字符的字符串 s，如果 a 的左边没有 b，b 的右边没有 a 则认为 s 是平衡的。求使得 s 平衡需要删除的最少次数。
可以枚举分割线，分割线左侧的 b 都要删除，右侧的 a 也要删除，取最小值即可。可以使用前后缀分解来解决。
也可也使用动态规划，定义 dp[i] 表示前 i 个字符平衡需要删除的最小次数。
- 当
i是b时，dp[i] = dp[i - 1] - 当
i时a时，dp[i] = min(dp[i - 1] + 1, cntB)，其中cntB表示i前面的b的个数
代码
/**
* @date 2026-02-09 11:31
*/
public class MinimumDeletions1653 {
public int minimumDeletions(String s) {
int n = s.length();
int[] prefixB = new int[n + 1];
char[] chars = s.toCharArray();
for (int i = 0; i < n; i++) {
int c = chars[i] - 'a';
prefixB[i + 1] = prefixB[i] + c;
}
int deletedA = 0;
int res = Integer.MAX_VALUE;
for (int i = n - 1; i > 0; i--) {
int c = chars[i] - 'a';
if (c == 0) {
res = Math.min(res, prefixB[i] + deletedA);
deletedA++;
}
}
res = Math.min(res, deletedA);
return res;
}
}
性能
