题目链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/
# 解题思路
根据题目意思，最后字符串应该是 1）全是 a，2）全是 b，所有的 a 都在 b 的前面（即：aaaaaaaaabbbbbbb）
那么，可以枚举分割点来计算删除的最小字符数：
- 从左往右枚举 n + 1 个分割点，针对每一个分割点，左边必须全 a，右边必须全 b，两边删除的字符数求和就是点前分割点分割，达到平衡的删除字符数；如此取最小的即可
- 优化：
- 先统计从右到左子字符串中所有 a 的字符串，记录与数组
# 提交结果
# 代码
class Solution { | |
public int minimumDeletions(String s) { | |
char[] chs = s.toCharArray(); | |
int n = chs.length; | |
// [i, n - 1] 的 a 的数量 | |
int[] racount = new int[n]; | |
for (int i = n - 1; i >= 0; --i) { | |
racount[i] = chs[i] == 'a' ? 1 : 0; | |
if (i < n - 1) { | |
racount[i] += racount[i + 1]; | |
} | |
} | |
// 左边 b 的数量 | |
int lbcount = 0; | |
int res = Integer.MAX_VALUE; | |
// 枚举每一个分割点 | |
for (int i = 0; i < n; ++i) { | |
// [0, i) 为 a，[i, n - 1] 为 b | |
res = Math.min(res, lbcount + racount[i]); | |
lbcount += chs[i] == 'b' ? 1 : 0; | |
} | |
return Math.min(lbcount, res); | |
} | |
} |
