难度: Medium
给你一个字符串 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 <= 105s[i] 要么是 'a' 要么是 'b' 。运行时间: 164 ms
内存: 16.5 MB
class Solution:
def minimumDeletions(self, s: str) -> int:
a_cnt, b_cnt = 0, 0
for c in s:
if c == 'a':
if b_cnt > 0:
b_cnt -= 1
a_cnt += 1
else:
b_cnt += 1
return len(s) - a_cnt - b_cnt
该题解采用了一种贪心算法的思路。我们通过遍历字符串 s，计算在每个位置上保留字符 'a' 和 'b' 的最优数量。变量 a_cnt 用来记录保留的 'a' 的数量，而 b_cnt 用来记录保留的 'b' 的数量。遍历字符串时，每遇到一个 'a'，如果之前有 'b' 出现（即 b_cnt > 0），则意味着为了保持字符串平衡，我们可以选择删除这个 'b' 而不是当前的 'a'，因此 b_cnt 减一；如果没有 'b' 或者已经处理完所有 'b'，则增加 a_cnt。每遇到一个 'b'，直接增加 b_cnt。最后，字符串 s 的长度减去我们决定保留的 a_cnt 和 b_cnt 就是需要删除的最小字符数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minimumDeletions(self, s: str) -> int:
a_cnt, b_cnt = 0, 0 # 初始化保留的'a'和'b'的计数器
for c in s: # 遍历字符串中的每个字符
if c == 'a':
if b_cnt > 0: # 如果之前已经计数了'b'，可以考虑删除一个'b'来保持平衡
b_cnt -= 1
a_cnt += 1 # 增加'a'的计数
else:
b_cnt += 1 # 增加'b'的计数
# 返回需要删除的最小字符数，即总长度减去保留的'a'和'b'的数量
return len(s) - a_cnt - b_cnt
这种处理逻辑基于贪心算法的思维，旨在最小化删除操作的数量来达到平衡。当我们遇到一个'a'且之前已经有累积的'b'（b_cnt > 0）时，为了使得字符串更接近平衡（即'a'和'b'的数量相等），选择删除一个先前计数的'b'，而非简单地增加'a'的数量。这样做可以有效减少需要调整的后续操作，因为我们通过减少一个已存在的不平衡（多余的'b'），而不是增加新的不平衡（过多的'a'）。
如果字符串s全部由'b'组成，这意味着在遍历字符串过程中没有遇到任何'a'，因此b_cnt将等于字符串s的长度（因为每遇到一个'b'，b_cnt就增加1）。由于没有'a'来触发删除'b'的操作，最终的删除次数将是0，因为所有的'b'都被保留了。这种情况下，字符串虽然不平衡（只有'b'没有'a'），但根据题解的逻辑，没有执行任何删除操作，因此删除次数为0。
题解中的删除字符操作主要通过减少出现次数较多的字符（在遇到另一字符时）来尽量减少总体的不平衡。这种策略通常能确保字符串尽可能接近平衡，但不保证完全平衡。例如，如果一个字符从未出现，则另一个字符永远不会被删除，结果是一个单一字符的字符串。此外，如果'a'和'b'的数量极为接近，每次删除都可能导致必须更多地依赖于字符串的初始顺序和配置，这可能会导致一些边缘案例在平衡性上不是最优的。
题解中的贪心策略在大多数情况下是有效的，包括当一个字符的数量显著多于另一个字符时。在极端情况下，如字符串几乎全是'a'只有一个'b'，这个策略仍然有效，因为它会计算出只需删除一个'b'，即可使字符串尽可能接近平衡。这种情况下，尽管字符串的平衡性并不完美（因为几乎全是'a'），但考虑到删除数量最少的目标，这种处理方式仍然是合理的。