使字符串平衡的最少删除次数（简单动态规划）

给你一个字符串 s ，它仅包含字符 a 和 b​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = b 的同时 s[j]= a，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例：

input

s = "aababbab"

output

2

思路：
假设到i之前的字符串都是平衡的。对于当前位置i来说，
如果s[i] = a，那么处理方法能有两种：

• 将当前的字符a删除；
• 保留当前的字符a，将i之前的所有b都删除。
• 对于这两种操作取最小值，即为将s(1, i)变为平衡串的最小操作数。

如果s[i] = b，则不影响字符串平衡，所以不做处理。

在做完以上操作后，s(1, i)一定能成为一个平衡的串，我们也已知了将s(1, i)变为平衡串的最小操作数。所以对于i + 1也只需要做相同的操作即可。

代码：

class Solution {
public:int minimumDeletions(string s) {int countb = 0, ans = 0;for(int i = 0; i < s.size(); ++ i) {if(s[i] == 'a') {ans = min(ans + 1, countb);} else {countb ++;}}return ans;}
};