Easy

题目描述

给你一个仅由大写英文字母组成的字符串 s。

你可以对这个字符串执行一些操作，在每次操作中，你可以从 s 中删除任何一个子字符串 "AB" 或 "CD"。

请你删除所有可以删除的子字符串，返回可能得到的最小长度。

注意，删除子字符串后，余下的字符会连在一起，可能会产生新的 "AB" 或 "CD" 子字符串。

示例 1：

输入：s = "ABFCACDB"
输出：2
解释：我们可以执行下述操作：
- 删除子字符串 "ABFCACDB"，所以 s = "FCACDB"。
- 删除子字符串 "FCACDB"，所以 s = "FCAB"。  
- 删除子字符串 "FCAB"，所以 s = "FC"。
所以字符串的最终长度为 2。
可以证明 2 是可以获得的最小长度。

示例 2：

输入：s = "ACBBD"
输出：5
解释：无法对该字符串执行操作，所以长度保持不变。

提示：

  • 1 <= s.length <= 100
  • s 仅由大写英文字母组成

解题思路

这道题有两种常见的解法：

方法一：暴力模拟法 反复遍历字符串，寻找并删除 “AB” 或 “CD” 子串，直到无法再删除为止。每次找到目标子串就删除，然后重新开始遍历。这种方法简单直观，时间复杂度较高但对于题目约束范围完全可行。

方法二：栈模拟法（推荐） 使用栈来模拟删除过程。遍历字符串的每个字符：

  • 如果栈不为空且当前字符与栈顶字符能组成 “AB” 或 “CD”，则弹出栈顶字符（相当于删除这对字符）
  • 否则将当前字符入栈

具体判断逻辑：

  • 当前字符是 ‘B’ 且栈顶是 ‘A’，删除 “AB”
  • 当前字符是 ‘D’ 且栈顶是 ‘C’，删除 “CD”
  • 其他情况则入栈

栈的特性天然适合处理这类配对删除问题，一次遍历即可完成，效率更高。最终栈的大小就是最小长度。

两种方法中，栈解法更优雅且时间复杂度更低，是首选解法。

代码实现

class Solution {
public:
    int minLength(string s) {
        stack<char> st;
        
        for (char c : s) {
            if (!st.empty() && 
                ((c == 'B' && st.top() == 'A') || 
                 (c == 'D' && st.top() == 'C'))) {
                st.pop();
            } else {
                st.push(c);
            }
        }
        
        return st.size();
    }
};

class Solution:
    def minLength(self, s: str) -> int:
        stack = []
        
        for c in s:
            if stack and ((c == 'B' and stack[-1] == 'A') or 
                         (c == 'D' and stack[-1] == 'C')):
                stack.pop()
            else:
                stack.append(c)
        
        return len(stack)

public class Solution {
    public int MinLength(string s) {
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in s) {
            if (stack.Count > 0 && 
                ((c == 'B' && stack.Peek() == 'A') || 
                 (c == 'D' && stack.Peek() == 'C'))) {
                stack.Pop();
            } else {
                stack.Push(c);
            }
        }
        
        return stack.Count;
    }
}

var minLength = function(s) {
    let stack = [];
    
    for (let char of s) {
        if (stack.length > 0) {
            let top = stack[stack.length - 1];
            if ((top === 'A' && char === 'B') || (top === 'C' && char === 'D')) {
                stack.pop();
                continue;
            }
        }
        stack.push(char);
    }
    
    return stack.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈解法暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(1)

说明：

  • 栈解法：每个字符最多入栈出栈一次，时间复杂度 O(n)；最坏情况下所有字符都入栈，空间复杂度 O(n)
  • 暴力解法：每轮最多删除一个子串，最坏需要 n/2 轮，每轮遍历剩余字符串，时间复杂度 O(n²)；原地修改字符串，空间复杂度 O(1)