Medium

题目描述

给你一个字符串 s，它仅包含字符 'a' 和 'b'。

你可以删除 s 中任意数量的字符，使 s 平衡。当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 和 s[j] = 'a' 时，s 是平衡的。

返回使 s 平衡的最少删除次数。

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
删除下标 2 和 6 处的字符（"aababbab" -> "aaabbb"），或者
删除下标 3 和 6 处的字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的解决方案是删除前两个字符。

提示：

  • 1 <= s.length <= 10^5
  • s[i] 为 'a' 或 'b'

解题思路

解题思路

这道题要求删除最少字符使字符串平衡，即不存在 'b' 在 'a' 前面的情况。

方法一：前缀后缀统计法

我们可以枚举分割点，将字符串分为两部分：左边全是 'a'，右边全是 'b'。对于每个分割点 i，计算：

  • 左边需要删除的 'b' 个数
  • 右边需要删除的 'a' 个数

预处理前缀 'b' 个数和后缀 'a' 个数，然后枚举所有分割点找最小值。

方法二：动态规划法（推荐）

用 dp 表示当前位置保持平衡需要的最少删除数。对于每个字符：

  • 遇到 'a'：要么删除这个 'a'（删除数 +1），要么删除前面所有的 'b'
  • 遇到 'b'：记录 'b' 的个数，为后续可能的删除做准备

状态转移：dp[i] = min(dp[i-1] + (s[i] == 'a'), b_count)

方法三：栈模拟法

使用栈来模拟删除过程，遇到 'ba' 模式时进行删除操作。

代码实现

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.length();
        int b_count = 0;
        int deletions = 0;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == 'b') {
                b_count++;
            } else {
                // 遇到 'a'，要么删除这个 'a'，要么删除前面所有的 'b'
                deletions = min(deletions + 1, b_count);
            }
        }
        
        return deletions;
    }
};

class Solution:
    def minimumDeletions(self, s: str) -> int:
        b_count = 0
        deletions = 0
        
        for char in s:
            if char == 'b':
                b_count += 1
            else:
                # 遇到 'a'，要么删除这个 'a'，要么删除前面所有的 'b'
                deletions = min(deletions + 1, b_count)
        
        return deletions

public class Solution {
    public int MinimumDeletions(string s) {
        int bCount = 0;
        int deletions = 0;
        
        foreach (char c in s) {
            if (c == 'b') {
                bCount++;
            } else {
                // 遇到 'a'，要么删除这个 'a'，要么删除前面所有的 'b'
                deletions = Math.Min(deletions + 1, bCount);
            }
        }
        
        return deletions;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minimumDeletions = function(s) {
    let bCount = 0;
    let deletions = 0;
    
    for (let char of s) {
        if (char === 'b') {
            bCount++;
        } else {
            deletions = Math.min(deletions + 1, bCount);
        }
    }
    
    return deletions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划法前缀后缀法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

说明：

  • 动态规划法只需要一次遍历，空间复杂度为常数级别
  • 前缀后缀法需要预处理数组，空间复杂度为 O(n)
  • 推荐使用动态规划法，效率最高

相关题目