题目

给你一个字符串 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' 。

解题思路

题目要求字符串变得“平衡”。“平衡”的定义是不存在 b 在 a 之前。

这意味着，处理后的字符串必须长成这个样子：

$$A...AB...B$$

即：前面全是 'a'（也可以没有），后面全是 'b'（也可以没有）。

我们有两种主要的解题思路：

思路一：枚举分割点（前缀和/后缀和思想）

这是最直观的思路。既然最终结果一定是 aaaa...abbbb... 的形式，我们可以想象在字符串中画一条竖线，竖线左边必须全是 'a'，竖线右边必须全是 'b'。

逻辑步骤：

分割线位置： 我们遍历字符串的每一个缝隙（包括最左边和最右边），假设这个缝隙就是 a 和 b 的分界线。
计算代价： 对于每一个分割点：
- 左边部分： 需要删掉所有的 'b'。
- 右边部分： 需要删掉所有的 'a'。
- 当前代价 = (左边的 'b' 个数) + (右边的 'a' 个数)。
优化： 如果暴力计算，每次都要遍历左右，复杂度是 $O(N^2)$。但我们可以预处理：
- 先遍历一遍统计出总共有多少个 'a' (记为 total_a)。
- 再遍历一遍字符串，维护一个变量 count_b (当前左边遇到的 'b' 个数)。
- 此时，右边的 'a' 个数 = total_a - count_a (当前遇到的 'a' 个数)。
- 或者更简单：右边的 'a' 个数 = total_a - (当前位置下标 - 当前 count_b)？不如直接维护右边剩余的 'a'。

算法流程 ($O(N)$)：

统计整个字符串中 'a' 的总数，赋值给 right_a。
初始化 left_b = 0。
初始化 min_deletions = right_a (相当于分割线在最左边，把所有 'a' 全删了，全保留 'b')。
遍历字符串 s 中的每个字符 c：
- 如果 c == 'a'：说明这个 'a' 从分割线右边跑到了左边（被划入左半区），那么 right_a 减 1。
- 如果 c == 'b'：说明这个 'b' 留在了分割线左边，需要被删除，left_b 加 1。
- 每次迭代更新：min_deletions = min(min_deletions, left_b + right_a)。
返回 min_deletions。

思路二：动态规划 / 贪心 (最优解法)

这个思路更符合算法直觉，通常代码更简洁。我们可以把问题看作：“当我们遍历到第 i 个字符时，如果要使 s[0...i] 平衡，最少需要删几次？”

定义两个变量：

count_b：目前为止遇到的 'b' 的数量。
dp：目前为止使字符串平衡的最少删除次数。

状态转移逻辑： 当我们遍历到一个新字符 c 时：

如果 c == 'b'：
- 在这个 'b' 之前如果已经是平衡的，加上这个 'b' 依然平衡（因为 'b' 可以接在 'a' 或 'b' 后面）。
- 我们不需要删除它。
- 操作：count_b 加 1，dp 不变。
如果 c == 'a'：
- 这就出问题了。如果前面有 'b'，这个 'a' 就破坏了平衡。我们有两个选择：
  - 选项 A（删当前）： 把这个刚进来的 'a' 删掉。代价是之前的最小代价 dp + 1。
  - 选项 B（保留当前）： 如果我们要保留这个 'a'，那意味着它前面不能有任何 'b'。所以我们要把前面所有的 'b' 都删掉。代价是 count_b。
- 决策： 我们取两者的最小值。
- 操作：dp = min(dp + 1, count_b)。

举例 bbaaaaabb：

b: count_b=1, dp=0
b: count_b=2, dp=0
a: 遇到 'a'。删它(dp=1) vs 删前面的b(count_b=2)。取小 -> dp=1。
a: 遇到 'a'。删它(dp=1+1=2) vs 删前面的b(count_b=2)。取小 -> dp=2。
a: 遇到 'a'。删它(dp=2+1=3) vs 删前面的b(count_b=2)。取小 -> dp=2。
... 后面都是最优解保持 2。

这个思路相当于在比较：是把当前这个 'a' 视为“必须要删掉的噪音”，还是发现前面的 'b' 才是“噪音”。

具体代码

解法一

func minimumDeletions(s string) int {
    // 1. 先统计整个字符串中 'a' 的总数
    rightA := 0
    for _, char := range s {
        if char == 'a' {
            rightA++
        }
    }

    // 初始状态：分割点在字符串最左侧
    // 需要删除的只有右边的所有 'a'（左边为空，没有 'b' 需要删）
    minDel := rightA 
    leftB := 0

    // 2. 遍历字符串，模拟分割点向右移动
    for _, char := range s {
        if char == 'a' {
            // 如果当前字符是 'a'，它从分割线右边移到了左边
            // 它是合法的（左边允许有 'a'），所以不需要删除了
            // 右边剩余的 'a' 减少一个
            rightA--
        } else {
            // 如果当前字符是 'b'，它从分割线右边移到了左边
            // 它是非法的（左边不能有 'b'），所以必须删除
            // 左边需要删除的 'b' 增加一个
            leftB++
        }

        // 计算当前分割点的总删除次数 = 左边删掉的 'b' + 右边删掉的 'a'
        // 并更新全局最小值
        if cost := leftB + rightA; cost < minDel {
            minDel = cost
        }
    }

    return minDel
}

解法二

func minimumDeletions(s string) int {
    bCount := 0
    dp := 0 // dp[i] 的空间优化版，表示处理到当前字符时的最小删除次数

    for _, char := range s {
        if char == 'b' {
            // 遇到 'b'，对平衡性没有直接破坏（'b' 可以放在最后）
            // 只是增加了潜在的“如果后面出现 'a' 需要删除前面所有 'b'”的代价
            bCount++
        } else {
            // 遇到 'a'，出现冲突
            // 决策 1: 删除当前的 'a' -> 代价是 dp + 1
            // 决策 2: 保留当前的 'a' -> 意味着前面所有的 'b' 都得删掉，代价是 bCount
            // 取两者的最小值
            if dp + 1 < bCount {
                dp = dp + 1
            } else {
                dp = bCount
            }
        }
    }

    return dp
}

1653. 使字符串平衡的最少删除次数

beautifulremi

题目

解题思路

思路一：枚举分割点（前缀和/后缀和思想）

思路二：动态规划 / 贪心 (最优解法)

具体代码

解法一

解法二