1653. 使字符串平衡的最少删除次数
给你一个字符串 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'。解答：动态规划
class Solution {
public int minimumDeletions(String s) {
// 初始化结果为 0，b 记录字符串中出现的 b 的个数
int res=0,b=0;
for(char c:s.toCharArray()){
// 末尾出现a的时候，2个选择：1、删除这个a，然后将s[0,i-1]变平衡；
//2、保留这个a，删除前面所有的b
if(c=='a'){
// 将结果更新为 res 和 b 中较小的一个，并加 1
res=Math.min(res+1,b);
}
// 如果当前字符为 b
else{
// 出现b的时候，最后面的b不需要删除，dp不变，b的个数加1就好
b++;
}
}
// 返回结果
return res;
}
}
