DSA sheet · Stack · Simulation & undo pattern

Remove All Adjacent Duplicates In String

The second problem of the simulation and undo pattern. Two equal letters standing side by side cancel each other, and after they vanish, the letters around them become neighbours and may cancel too. The teacher first writes a brute force that keeps scanning the string again and again until nothing changes, shows why it is O(n²) in the worst case (TLE for n = 10⁵), then switches to a stack for O(n). Finally she makes an interview point: the same stack idea written with a string builder runs faster, and she explains why.

Why it matters: this "compare with the top, cancel or push" loop is the template for the next two problems (Make The String Great, Min Length After Removing Substrings). Learn it once here.

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)
• Part A · Brute force: scan again and again with a flag
• Part B · Stack: compare with the top
• Part C · Same idea, builder instead of a stack (the interview point)
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile where you only touch the top, like a pile of plates. The last plate you put on is the first one you take off: LIFO, Last In First Out.

stack = []
stack.append('a')      # push -> ['a']
stack.append('b')      # push -> ['a', 'b']     top is 'b'
if stack and stack[-1] == 'b':   # check empty BEFORE peeking
    stack.pop()        # pop  -> ['a']

The undo pattern

We read the input left to right. Each new item looks at the most recent item that is still alive (the top). If they cancel, we pop the top and drop the new item. If not, we push the new item. The stack is perfect here because, after a pop, the item underneath automatically becomes the new "most recent" one, ready to be compared with the next item. That's exactly the "after one pair vanishes, the neighbours meet" effect this problem needs.

Strings are immutable

Immutable = can't be changed in place. Deleting from the middle of a string means building a new string, which copies everything: O(n) per change. So we build the answer separately, in a list (Python) or a StringBuilder (Java), and join it into a string at the end.

The TLE rule the teacher uses

Roughly, about 10⁸ simple operations is the limit before TLE (Time Limit Exceeded). Around 4–5·10⁸ sometimes still passes if the code is simple, but once you reach 10⁹ or more, it will surely fail.

Part A · Brute force: scan again and again with a flag

LeetCode 1047

1The question in simple words

You get a string s of lowercase letters. A removal means: pick two adjacent (side by side) letters that are equal, and delete both. Keep doing removals until no two equal letters are next to each other. Return the final string. (LeetCode promises the final answer is the same whatever order you remove in.)

Notice the chain reaction: the two a's were not neighbours at the start. They only meet after the b's disappear. That's the whole difficulty of the problem.

Another example: "azxxzy" → remove "xx" → "azzy" → remove "zz" → "ay".

2What the constraints tell us

• 1 ≤ s.length ≤ 10⁵. An O(n²) solution would be 10¹⁰ steps → definitely TLE. So we need about O(n). The teacher still writes the brute force first, to understand the problem.
• Only lowercase English letters, so "equal" is a plain ==. (In the next problem, case will matter.)
• The string has at least 1 letter, but the answer can be empty (e.g. "aa" → "").

3Intuition: delete pairs, then check again

The natural first idea: walk with an index i. If s[i] and s[i+1] are the same, they're a duplicate pair, so don't copy them. Otherwise copy s[i] into a new string (call it s1). Because strings can't be changed, we build the result in a separate builder.

But one scan isn't enough. In "abbaca", the first scan removes "bb" and gives "aaca". The two a's only became neighbours because of that removal. So we have to scan again. And again, until a whole scan removes nothing.

4Building the logic from the example

One scan over "abbaca"

1. i = 0: 'a' vs next 'b' → different → copy 'a'. s1 = "a".
2. i = 1: 'b' vs next 'b' → same → this is a pair, skip both (jump i to 3).
3. i = 3: 'a' vs next 'c' → different → copy 'a'. s1 = "aa".
4. i = 4: 'c' vs 'a' → copy 'c'. i = 5: 'a' is the last letter → copy. s1 = "aaca".

Why the scan must repeat: the flag

After one scan we can't be sure we're done, because a removal may have created a new neighbour pair. So the teacher keeps a flag (a True/False variable, here removed):

• Before each scan, set removed = False.
• Whenever the scan deletes a pair, set removed = True, meaning "something changed, the letters around it might now match, so scan once more".
• Repeat scans while removed is True. A scan that deletes nothing proves the string is final.

For "abbaca": scan 1 → "aaca" (removed); scan 2 → "ca" (removed); scan 3 → "ca", nothing removed → stop. Three scans.

How slow is it? The teacher's worst case

For "abbaca" (length 6) we needed only 3 scans, so you might think it's "a bit more than O(n)". The number of scans depends on how the duplicates are arranged. We always judge by the worst case, so she builds a nasty one: "abcddcba".

Each scan removes just one pair from the middle. With n letters that's about n/2 scans, each costing O(n) → O(n²). For n = 10⁵ that's around 10¹⁰ steps → TLE. She submitted it and it did TLE.

5Approach steps

1. removed = True so the first scan happens.
2. While removed: set it to False, make an empty builder sb, and i = 0.
3. While i < n: if i + 1 < n and s[i] == s[i+1] → skip both (i += 2) and set removed = True. Else copy s[i] and i += 1.
4. After the scan, s = "".join(sb).
5. When a scan removes nothing, return s.

6Code (Python)

class Solution:
    def removeDuplicates(self, s):
        removed = True                       # run at least one scan
        while removed:
            removed = False                  # assume this scan changes nothing
            sb = []                          # the builder for this scan
            i = 0
            n = len(s)
            while i < n:
                if i + 1 < n and s[i] == s[i + 1]:
                    i += 2                   # skip the pair
                    removed = True           # something changed, scan again
                else:
                    sb.append(s[i])          # keep this letter
                    i += 1
            s = "".join(sb)                  # the new, shorter string
        return s

7Code line by line

8Dry run

s = "abbaca".

Answer "ca" ✓

9Complexity & remember

• Time O(n²) worst case: up to about n/2 scans × O(n) each (the "abcddcba" shape). For n = 10⁵ → TLE.
• Space O(n): the builder for each scan.

Part B · Stack: compare with the top

1The question (same as Part A)

Same question: keep deleting equal neighbour pairs until none is left. New goal: one single pass.

2What the constraints tell us

n up to 10⁵ → we need O(n) (or O(n log n)). One pass with O(1) work per letter is the target.

3Intuition: "I need to look back" → stack

The teacher spots the key moment in the brute force: after "bb" disappears, the next 'a' has to match with the previous 'a', which we already passed and stored. We're moving forward, but sometimes we must go back and delete the latest kept letter. "Go back to the most recent one and delete it" = pop from a stack.

So the stack holds the letters we've kept so far, and its top is the latest one. For each new letter:

• if the top equals it → they're an adjacent pair in the final picture → pop the top and don't push the new letter (both vanish);
• else → push it.

The chain reaction now happens for free. After a pop, the new top is the letter that sat before the removed pair, which is exactly the letter that now touches the next one.

4Building the logic from the example

"abbaca": push a; push b; next b equals top b → pop; next a equals top a → pop (that's the chain reaction, in one step!); push c; push a. Stack = [c, a] → "ca". One pass, no rescanning.

5Approach steps

1. Make an empty stack.
2. For each letter ch: if the stack isn't empty and its top equals ch → pop. Otherwise → push ch.
3. Join the stack (bottom to top) into a string and return it.

6Code (Python)

class Solution:
    def removeDuplicates(self, s):
        stack = []
        for ch in s:
            if stack and stack[-1] == ch:   # same as the latest kept letter?
                stack.pop()                 # both vanish
            else:
                stack.append(ch)            # keep it (for now)
        return "".join(stack)

7Code line by line

8Dry run (stack after every step)

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

Answer "ca" ✓. On "abcddcba" (the brute force's worst case) the stack grows to [a, b, c, d], then each next letter pops one: d, c, b, a → empty. Eight steps instead of five full scans.

9Complexity & remember

• Time O(n): each letter is pushed at most once and popped at most once.
• Space O(n): in the worst case nothing cancels and every letter stays on the stack. The teacher's example: "abcdabcdabcd…" has repeats, but never side by side, so everything is pushed.

Part C · Same idea, builder instead of a stack (the interview point)

1What changes

Look at the end of Part B: we fill a stack, then convert it to a string. The teacher asks: why not keep the answer in a string builder from the start, and treat its last character as the top? Appending at the end = push. Deleting the last character = pop. Both are O(1). The logic is still the stack logic; we just don't use a Stack object.

2Why the builder is faster (in Java)

Same Big-O, but it ran faster on LeetCode. Her reason: Java's Stack class is synchronized. Every push and pop takes a lock, a safety step for multi-threaded programs, and that costs time. A StringBuilder is a plain growable character array with no locks. Also, with the builder we skip the final "stack → string" conversion step. She says explaining this difference in an interview makes a strong impression.

3Code (Python, builder style)

class Solution:
    def removeDuplicates(self, s):
        sb = []                                  # the builder
        for ch in s:
            length = len(sb)
            if length > 0 and sb[length - 1] == ch:   # last char = top
                del sb[length - 1]               # delete last char (O(1))
            else:
                sb.append(ch)                    # append = push
        return "".join(sb)                       # builder -> string

The dry run is identical to Part B: the builder holds exactly what the stack held after every step ([a] → [a,b] → [a] → [ ] → [c] → [c,a]).

4Complexity & remember

• Time O(n), space O(n), like Part B, but with a smaller constant in Java (no locks, no final conversion).

Part D · Revision page

s = Solution()
print(s.removeDuplicates("abbaca"))     # ca
print(s.removeDuplicates("azxxzy"))     # ay
print(s.removeDuplicates("abcddcba"))   # (empty string)
print(s.removeDuplicates("aaa"))        # a
print(s.removeDuplicates("abcd"))       # abcd

Based on this video: Remove All Adjacent Duplicates In String | Stack simulation & undo pattern