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"）。
class Solution:
def minimumDeletions(self, s: str) -> int:
'''
f[i] 表示前i个字符变平衡的最少删除次数
对于字符串s的前i位
1.如果最后一位s[i-1]=='b'，则他变为平衡的操作次数和 前i-1位的相同，即f[i]=f[i-1]
2.如果s[i-1]=='a',为了不让b在a的前面，可以在前i-1位平衡的基础上删除当前的a，次数变为f[i]=f[i-1]+1
或者将前i位中所有的b删除掉，次数变为f[i]=cntb，最终取其中次数小的，即f[i]=min(f[i-1]+1,cntb)
递推方向：根据字符串长度，从1开始递推即可
'''
n=len(s)
f=[0]*(n+1)
cntb=0
for i in range(1,n+1):
# 如果最后一位是b，则不需要删
if s[i-1]=='b':
cntb+=1
f[i]=f[i-1]
else:
# 是a的话，要么删掉a之后平衡，或者删除a前面所有的b平衡，两种情况取较小值
f[i]=min(f[i-1]+1,cntb)
return f[n]