给你一个字符串 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 <= 105
s[i] 要么是 ‘a’ 要么是 ‘b’ 。
这道题其实不难，自己考虑复杂了
关键点在于把每种可能想清楚
想要达到平衡就是a的左边无b，b的右边无a
对于具体的字符串可分为：
1.全a 2.全b 3.有a和b，a的左边无b，b的右边无a
其实1和2 是3的特殊情况（为0时）
我们想统计a的个数，赋值给righta
然后再遍历，如果是a，当前righta-1否则leftb+1
并判断leftb+righta是否小于当前最小值，是则更新，注意l一开始和righta相等
class Solution:
def minimumDeletions(self, s: str) -> int:
l=len(s)
leftb=0
righta=0
for i in range(l):
if s[i]=='a':
righta+=1
t=righta
for i in range(l):
if s[i]=='a':
righta-=1
else:
leftb+=1
t=min(t,leftb+righta)
return t
复杂度分析
时间复杂度：O(n)，其中 n 是 s的长度。需要遍历两遍 s，第一遍计算出 s 中 “a” 的数量，第二遍遍历所有的间隔，求出最小需要删除的字符数。
空间复杂度：O(1)，只需要常数空间。
动态规划思想：
动态规划
平衡字符串要求每一个a之前不能有b（或每一个b之后不能有a），考虑每一位a（或b）是否保留；
对于字符串s[0i]，如果保留最后一位a，那么就将它之前的b全部删掉，删除次数d[i]=这个a之前b的个数；若不保留，则删掉这个a后同时也要让s[0i-1]平衡的删除次数最小，删除次数就是1+d[i-1]；取两者较小值即可；
即d[i]=min{cnt[i], 1 + d[i-1]}，cnt[i]为当前遇到的最后一个a之前b的个数，d[i]可仅由i和i-1递推，因此可以只用一个变量维护d[i]；
class Solution {
public int minimumDeletions(String s) {
int n = s.length();
char[] ch = s.toCharArray();
int res = 0, cnt = 0;
for (char c : ch) {
if (c == 'b') cnt++;
else res = Math.min(cnt, 1 + res);
}
return res;
}
}