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

dp, https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/

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

这个问题可以通过动态规划的思想来解决。

解题思路

一个字符串是“平衡”的，意味着所有的 'a' 都在所有的 'b' 之前。换句话说，不存在 'b' 出现在 'a' 前面的情况。

当我们从左到右遍历字符串时，对于当前字符，为了保持平衡，我们面临两种选择：

如果当前字符是 'b'：它不会破坏已经平衡的现有前缀（因为 'b' 放在末尾是符合规则的）。我们只需要记录目前为止遇到的 'b' 的数量，以便后续遇到 'a' 时做决策。
如果当前字符是 'a'：它可能会破坏平衡（如果前面已经出现了 'b'）。此时我们有两种策略：
- 策略 A：删除这个 'a'。删除次数就是在处理前一个字符时的最小删除次数加 1。
- 策略 B：保留这个 'a'。为了让这个 'a' 合法，我们必须删除前面出现过的所有 'b'。

我们取这两种策略的最小值作为当前位置的最优解。

算法步骤

初始化 res = 0（记录当前最小删除次数）。
初始化 count_b = 0（记录当前遇到的 'b' 的数量）。
遍历字符串中的每个字符 char：
- 如果 char 是 'b'，则 count_b += 1。
- 如果 char 是 'a'，则更新 res = min(res + 1, count_b)。
  - res + 1 代表删除当前的这个 'a'。
  - count_b 代表保留当前的 'a'，从而必须删除之前所有的 'b'。
最后返回 res。

代码实现

python

class Solution:
    def minimumDeletions(self, s: str) -> int:
        # res 存储使当前前缀平衡的最少删除次数
        res = 0
        # count_b 记录遍历过程中遇到的 'b' 的数量
        count_b = 0
        
        for char in s:
            if char == 'b':
                # 遇到 'b'，暂时不影响平衡，只需计数
                count_b += 1
            else:
                # 遇到 'a'，为了维持平衡，有两个选择：
                # 1. 删除当前的 'a'，步数增加 1 (res + 1)
                # 2. 保留当前的 'a'，意味着必须删除前面所有的 'b' (count_b)
                res = min(res + 1, count_b)
                
        return res

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是字符串的长度。我们只需要遍历一遍字符串。
空间复杂度： $O (1)$ ，只使用了两个额外的整数变量。

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

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