What is the main strategy for Minimum String Length After Removing Substrings?

Use a stack to push characters and remove AB or CD whenever they appear on top, ensuring minimal string length efficiently.

Can we solve this problem with brute force?

Brute force is possible but inefficient; it cannot scale due to exponential removal combinations. Stack simulation is optimal.

Why do we check only the top of the stack for removals?

Because only the last inserted characters can form AB or CD with the current character, ensuring correct minimal length.

What is the time and space complexity?

Time complexity is O(n) and space complexity is O(n), where n is the length of the input string.

Does the order of removals affect the final string length?

Stack simulation ensures all necessary removals are applied in order, so the final minimal length is achieved regardless of intermediate choices.

#2696

Easy

auto_awesome栈·状态

LeetCode 题解工作台

删除子串后的字符串最小长度

给你一个仅由大写英文字符组成的字符串 s 。你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除任一个 "AB" 或 "CD" 子字符串。通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的最小可能长度。注意，删除子串后，重新连接出的字符串可…

字符串栈模拟

题目描述

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

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

通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的最小可能长度。

注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：栈

我们遍历字符串 $s$ ，对于当前遍历到的字符 $c$ ，如果栈不为空且栈顶元素 $top$ 与 $c$ 可以组成 $AB$ 或 $CD$ ，则弹出栈顶元素，否则将 $c$ 入栈。

最后栈中剩余的元素个数就是最终字符串的长度。

在实现上，我们可以在栈中预先放入一个空字符，这样就不需要在遍历字符串时判断栈是否为空了，最后返回栈的大小减一即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is pushed and popped at most once. Space complexity is O(n) for the stack storing intermediate characters.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Mentions repeated removal of substrings AB or CD.
question_mark
Hints at using a stack to maintain current string state.
question_mark
Asks about handling overlapping patterns efficiently.

warning

常见陷阱

外企场景

error
Trying brute-force removal of all substring combinations instead of stack-based tracking.
error
Failing to check the top of the stack after each character push.
error
Assuming non-overlapping removals are sufficient, missing cases where removals create new AB or CD sequences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Remove different fixed-length substrings beyond AB or CD using the same stack method.
arrow_right_alt
Allow removal of substrings with variable lengths but fixed patterns.
arrow_right_alt
Compute the minimum string length if only one type of substring is removable.

help

常见问题

外企场景

继续练习

#2390 从字符串中移除星号 #2296 设计一个文本编辑器 #3174 清除数字