DSA sheet · Stack · Simulation & undo pattern

Minimum String Length After Removing Substrings

The last problem of the simulation and undo pattern. The teacher says that if you've done Remove All Adjacent Duplicates and Make The String Great, you can solve this one alone, and she's right. The loop is identical. Only the cancel rule changes: "A" followed by "B", or "C" followed by "D", vanish. And we return a length, not a string. She covers the "go back and delete" brute force, the stack, and the faster string-builder version, plus some useful tips on when code really hits TLE.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (stack, the undo pattern, TLE limits)
• Part A · Brute force: delete in place and step back
• Part B · Stack: compare with the top
• Part C · Same idea, builder instead of a stack
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile where you only touch the top. The last item in is the first item out: LIFO (Last In, First Out).

The undo pattern

Read left to right. The top of the stack is the latest surviving character. If the new character and the top together form something removable, pop the top and don't push the new one. Otherwise push. After a pop, the next character below becomes the top, which is exactly the character that now sits next to whatever comes after. So chain reactions ("removing AB makes a new CD appear") are handled for free.

The teacher's TLE tips (said in this video)

• On LeetCode, roughly 10⁸ operations is safe. Even 5·10⁸ may pass, slowly, if the code is simple.
• If the code is heavy or complex, you can get TLE even around 10⁷.
• Recursion has extra overhead too. She'll cover that later in the playlist.

Part A · Brute force: delete in place and step back

LeetCode 2696

1The question in simple words

You get a string s of uppercase letters. In one move you may delete any occurrence of the substring "AB" or "CD" (a substring = characters sitting next to each other, in that order). After a deletion, the two sides join and can form new "AB" or "CD". Return the minimum possible length of the string at the end.

Put simply: when you stand on a B and the previous character is an A, both can go. When you stand on a D and the previous one is a C, both can go. Same as the last two problems, just a different pair rule.

"ABFCACDB" → delete "AB" → "FCACDB" → delete "CD" → "FCAB" → now "AB" has formed → delete → "FC". Length 2.

Another: "ACBBD" → there's no "AB" or "CD" anywhere ("AC", "CB", "BB", "BD") → nothing can be removed → 5.

2What the constraints tell us

• 1 ≤ s.length ≤ 100. Very small: n² = 10⁴ steps. The brute force will be accepted easily (see the TLE tips in Part 0).
• Only uppercase English letters. No case conversion is needed this time, unlike Make The String Great.
• The answer can be 0 (everything removed, e.g. "CABD").

3Intuition: check the previous character, delete, look back again

Walk through the string with a simple loop. At each character, look at the previous one. If together they're "AB" or "CD", delete both. But now the character before them touches the character after them, so you have to go back and check again. That's the same back-and-forth we saw in the last two problems.

4Building the logic from the example

1. At A (index 0): nothing before it, nothing to do.
2. At B: the previous is A → "AB" → delete both. String: "FCACDB".
3. At F, then C, A, C: no pair ("FC", "CA", "AC" aren't removable).
4. At D: the previous is C → "CD" → delete. String: "FCAB". We must look back: the A before the hole now touches the B after it.
5. At B: the previous is A → "AB" → delete. String: "FC". Done → length 2.

Every deletion in the middle of a string shifts the rest left (O(n)), and we keep stepping back. The teacher's question: "where have we seen go back and check the previous one before?" → the stack.

5Approach steps

1. Copy s into a list arr. Set i = 1 (the "current" character; i − 1 is the previous one).
2. While i < len(arr): if arr[i−1] + arr[i] is "AB" or "CD" → delete both, and step back (i -= 1, but not below 1).
3. Else i += 1.
4. Return len(arr).

6Code (Python)

class Solution:
    def minLength(self, s):
        arr = list(s)
        i = 1                                   # current char; i-1 = previous
        while i < len(arr):
            pair = arr[i - 1] + arr[i]
            if pair == "AB" or pair == "CD":
                del arr[i - 1:i + 1]            # O(n) shift
                if i > 1:
                    i -= 1                      # new neighbours, look back
            else:
                i += 1
        return len(arr)

7Code line by line

8Dry run

s = "ABFCACDB".

Answer 2 ✓

9Complexity & remember

• Time O(n²): each middle deletion costs O(n), and there can be up to n/2 of them. With n ≤ 100 that's tiny, so it's accepted.
• Space O(n) for the list copy.

Part B · Stack: compare with the top

1The question (same as Part A)

Same question, one pass, O(1) work per character.

2What the constraints tell us

n ≤ 100, so we don't strictly need it. But "look back at the previous survivor" is the stack signal, and this is the version interviewers expect.

3Intuition

The stack holds the characters that survive so far, and its top is the "previous character" of the brute force. For each new ch:

• stack empty → nothing to pair with → push;
• top is 'A' and ch is 'B', or top is 'C' and ch is 'D' → pop the top, don't push ch (both excluded);
• otherwise → push ch.

At the end, the number of characters left on the stack is the answer: len(stack).

4Building the logic from the example

"ABFCACDB": A → push. B with top A → pop (A and B both excluded). F, C, A, C → no pop condition → push all four. D with top C → pop. B with top A → pop. Stack = [F, C] → 2. The teacher points out that the F-C-A-C stretch has no popping condition, so they just pile up until D and B arrive and unwind them.

5Approach steps

1. Empty stack.
2. For each ch: if the stack is non-empty and (top, ch) is ('A','B') or ('C','D') → pop. Else push ch.
3. Return len(stack).

6Code (Python)

class Solution:
    def minLength(self, s):
        stack = []
        for ch in s:
            if stack and ((stack[-1] == "A" and ch == "B") or
                          (stack[-1] == "C" and ch == "D")):
                stack.pop()              # "AB" or "CD" vanishes
            else:
                stack.append(ch)
        return len(stack)                # how many survived

7Code line by line

8Dry run (stack after every step)

s = "ABFCACDB". Stack drawn left = bottom, right = top.

Answer len(stack) = 2 ✓

9Complexity & remember

• Time O(n): one pass; each character is pushed once and popped at most once.
• Space O(n): the stack. Worst case, nothing is removable ("ACBBD") and everything is pushed.

Part C · Same idea, builder instead of a stack

1What changes

Exactly as in the last two problems: use a string builder as the stack. Its last character is the top, deleting the last character is the pop, and appending is the push. The teacher writes it slightly differently this time, using continue:

• If the builder isn't empty, read the last character.
• If (last, ch) is "AB" or "CD" → delete the last character and continue, which skips the rest of the loop body, so ch is never appended.
• The append line runs only when that continue did not happen.

At the end, return the builder's length. No toString is needed, since the answer is a number.

2Why it's faster, and what to say in an interview

Same Big-O, but faster in Java: Stack is synchronized (it locks on every push and pop), while StringBuilder is a plain array with no locks. The teacher's advice: a stack solution is perfectly fine in an interview. If the interviewer pushes you to optimise further, the builder version is what they're hoping to hear.

3Code (Python, builder style with continue)

class Solution:
    def minLength(self, s):
        sb = []
        for ch in s:
            length = len(sb)
            if length > 0:
                last = sb[length - 1]
                if (last == "A" and ch == "B") or (last == "C" and ch == "D"):
                    del sb[length - 1]      # remove the A / C
                    continue                # and never add the B / D
            sb.append(ch)                   # reached only if no removal
        return len(sb)

Dry run: the same as Part B. The builder goes [A] → [ ] → [F] → [F,C] → [F,C,A] → [F,C,A,C] → [F,C,A] → [F,C] → length 2.

4Complexity & remember

• Time O(n), space O(n).

Part D · Revision page

The whole undo family side by side. Same loop, different cancel rule:

s = Solution()
print(s.minLength("ABFCACDB"))   # 2
print(s.minLength("ACBBD"))      # 5
print(s.minLength("CABD"))       # 0
print(s.minLength("BA"))         # 2
print(s.minLength("A"))          # 1

Based on this video: Minimum String Length After Removing Substrings | Stack simulation & undo pattern