Medium

题目描述

给你一个只包含字符 ‘a’ 和 ‘b’ 的字符串 s。

你可以重复移除任何满足 ‘a’ 字符数量等于 ‘b’ 字符数量的子字符串。每次移除后，字符串的剩余部分会无缝连接在一起。

返回执行任意次此类操作后字符串的最小可能长度。

示例 1：

输入：s = "aabbab"
输出：0
解释：子字符串 "aabbab" 有三个 'a' 和三个 'b'。由于它们的数量相等，我们可以直接移除整个字符串。最小长度是 0。

示例 2：

输入：s = "aaaa"
输出：4
解释："aaaa" 的每个子字符串都只包含 'a' 字符。无法移除任何子字符串，因此最小长度仍为 4。

示例 3：

输入：s = "aaabb"
输出：1
解释：首先，移除子字符串 "ab"，剩下 "aab"。然后，移除新的子字符串 "ab"，剩下 "a"。无法进一步移除，因此最小长度是 1。

约束条件：

  • 1 <= s.length <= 10^5
  • s[i] 是 ‘a’ 或 ‘b’

提示：

  • 最初移除最长的可能平衡子字符串
  • 设 ‘a’ 的数量为 count_a，‘b’ 的数量为 count_b。我们能从这些推导出最终长度吗？
  • 答案是 abs(count_a - count_b)

解题思路

这道题的关键在于理解平衡移除的本质。

核心思路

题目允许移除任何 ‘a’ 和 ‘b’ 数量相等的子字符串。经过分析，我们可以发现一个重要规律：无论怎样移除，最终剩余字符串的长度总是等于原字符串中 ‘a’ 和 ‘b’ 数量差的绝对值。

证明思路

  1. 每次移除都保持差值不变：每次移除的子字符串中 ‘a’ 和 ‘b’ 数量相等，因此移除操作不会改变整个字符串中 ‘a’ 和 ‘b’ 的数量差。

  2. 最终无法继续移除的情况：当字符串中只剩下一种字符（全是 ‘a’ 或全是 ‘b’）时，就无法找到平衡的子字符串进行移除了。此时剩余字符的数量正好等于原始差值。

  3. 贪心策略有效性：我们总是可以通过合适的移除顺序达到理论最小值，因为任何包含相等数量 ‘a’ 和 ‘b’ 的子字符串都可以被移除。

算法步骤

  1. 统计字符串中 ‘a’ 和 ‘b’ 的数量
  2. 返回两者数量差的绝对值

时间复杂度 O(n)，空间复杂度 O(1)，这是最优解法。

代码实现

class Solution {
public:
    int minLengthAfterRemovals(string s) {
        int count_a = 0, count_b = 0;
        for (char c : s) {
            if (c == 'a') {
                count_a++;
            } else {
                count_b++;
            }
        }
        return abs(count_a - count_b);
    }
};

class Solution:
    def minLengthAfterRemovals(self, s: str) -> int:
        count_a = s.count('a')
        count_b = s.count('b')
        return abs(count_a - count_b)

public class Solution {
    public int MinLengthAfterRemovals(string s) {
        int count_a = 0, count_b = 0;
        foreach (char c in s) {
            if (c == 'a') {
                count_a++;
            } else {
                count_b++;
            }
        }
        return Math.Abs(count_a - count_b);
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minLengthAfterRemovals = function(s) {
    let countA = 0;
    let countB = 0;
    
    for (let char of s) {
        if (char === 'a') {
            countA++;
        } else {
            countB++;
        }
    }
    
    return Math.abs(countA - countB);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串统计字符数量
空间复杂度O(1)只使用常数额外空间存储计数器