#2696

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Minimum String Length After Removing Substrings

Determine the smallest string length after repeatedly removing AB or CD substrings using stack-based simulation techniques.

string stack simulation

Problem Statement

You are given a string s containing only uppercase English letters. You may perform operations where any occurrence of the substring AB or CD can be removed in a single step.

Return the minimum possible length of s after applying these operations any number of times. The order of removals may affect intermediate states but the final length should be minimized.

Examples

Example 1

Input: s = "ABFCACDB"

Output: 2

We can do the following operations:

Remove the substring "ABFCACDB", so s = "FCACDB".
Remove the substring "FCACDB", so s = "FCAB".
Remove the substring "FCAB", so s = "FC". So the resulting length of the string is 2. It can be shown that it is the minimum length that we can obtain.

Example 2

Input: s = "ACBBD"

Output: 5

We cannot do any operations on the string so the length remains the same.

Constraints

1 <= s.length <= 100
s consists only of uppercase English letters.

Solution Approach

Stack Simulation

Iterate through each character and push it onto a stack. If the top two elements form AB or CD, pop them immediately. Continue until the string is fully processed.

Avoid Brute Force

Directly checking all removal combinations is inefficient. The stack-based approach automatically handles overlapping patterns and ensures minimal string length without exponential checks.

Track State Carefully

Always check the top of the stack after each insertion to see if a removable substring has formed. Missing this leads to incorrect lengths for certain input sequences.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Stack

We traverse the string $s$. For the current character $c$ we are traversing, if the stack is not empty and the top element of the stack $top$ can form $AB$ or $CD$ with $c$, then we pop the top element of the stack, otherwise we push $c$ into the stack.

1

2

3

4

5

6

7

8

9

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

Solution 2: One-liner

#### TypeScript

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2390 removing stars from a string #2296 design a text editor #3174 clear digits