Minimum String Length After Removing Substrings

Difficulty: Easy | Acceptance: 77.20% | Paid: No Topics: String, Stack, Simulation

You are given a string s consisting only of uppercase English letters.

You can apply the following operation on s any number of times:

Select a substring that is equal to “AB” or “CD”, and remove it from s.

Return the minimum possible length of s after performing the above operation any number of times.

• Examples
• Constraints
• Brute Force Simulation
• Stack-based Approach
• Two-pointer In-place

Examples

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "AB" (s = "FCACDB")
- Remove the substring "CD" (s = "FCAB")
- Remove the substring "AB" (s = "FC")
The length of the final string is 2.

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string, so the length remains 5.

Constraints

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

Brute Force Simulation

Intuition Repeatedly scan the string and remove all occurrences of “AB” and “CD” until no more such substrings exist.

Steps

• While “AB” or “CD” exists in the string, replace all occurrences with empty string
• Return the final length

class Solution:
    def minLength(self, s: str) -> int:
        while "AB" in s or "CD" in s:
            s = s.replace("AB", "")
            s = s.replace("CD", "")
        return len(s)

Complexity

• Time: O(n²) - In worst case, each pass removes only one pair
• Space: O(n) - For string manipulation
• Notes: Simple but inefficient for large inputs

Stack-based Approach

Intuition Use a stack to simulate the removal process. For each character, check if it forms “AB” or “CD” with the top of the stack.

Steps

• Iterate through each character in the string
• If stack is not empty and top character with current character forms “AB” or “CD”, pop from stack
• Otherwise, push current character onto stack
• Return the final stack size

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

Complexity

• Time: O(n) - Single pass through the string
• Space: O(n) - Stack can hold up to n characters
• Notes: Optimal time complexity with clear logic

Two-pointer In-place

Intuition Use the input string itself as a stack with a write pointer, achieving O(1) extra space.

Steps

• Convert string to mutable array
• Use write pointer to track current stack position
• For each character, place it at write position and check if it forms “AB” or “CD” with previous character
• If so, decrement write pointer (simulating pop); otherwise, increment it
• Return write pointer value as final length

class Solution:
    def minLength(self, s: str) -> int:
        s = list(s)
        write = 0
        for read in range(len(s)):
            s[write] = s[read]
            if write > 0 and ((s[write-1] == 'A' and s[write] == 'B') or (s[write-1] == 'C' and s[write] == 'D')):
                write -= 1
            else:
                write += 1
        return write

Complexity

• Time: O(n) - Single pass through the string
• Space: O(1) - Only using pointers, no extra data structures
• Notes: Most space-efficient solution