DSA sheet · Stack · Simulation & undo pattern

Backspace String Compare

This is the first problem of the third stack pattern: simulation and undo operations. Whenever a character in the input means "cancel what came just before", a stack is the natural tool, because the thing you cancel is always the most recent one. The teacher solves it three times: first the plain way (build the typed text in a string and delete from its end), then with a stack (same cost, but a much cleaner idea), and finally with two pointers walking from the right, which needs no extra space at all.

Why it matters: it's tagged Easy, but the teacher warns that interviewers often expect the O(1)-space version. It also teaches a lesson you'll use again: a problem can be a "stack problem" and still have a simpler, smarter solution without a stack.

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: build the typed string and delete from its end
• Part B · Stack: the cleaner way to undo
• Part C · Optimal: two pointers from the right, O(1) space
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of items where you can only touch the top. Think of a pile of plates: you put a new plate on top, and you take a plate from the top. The plate you put last is the first one you take out. This rule is called LIFO: Last In, First Out.

In Python we don't need a special class. A normal list works as a stack, as long as we only add and remove at the end (the end of the list is the top).

stack = []
stack.append('a')      # push  -> ['a']
stack.append('b')      # push  -> ['a', 'b']      'b' is on top
print(stack[-1])       # peek  -> 'b'
stack.pop()            # pop   -> ['a']
if stack:              # ALWAYS check before pop / peek
    stack.pop()        #       -> []

The undo pattern

In this pattern we read the input from left to right. Normal items are pushed. A special item means "undo the latest one", so we pop. Why does a stack fit so well? Because the thing we must undo is always the most recent item that is still alive, and that is exactly the top of the stack. After a pop, the item below becomes the new "most recent", so a second undo removes it. That's how several undos in a row work automatically.

Your phone's keyboard works the same way: each backspace deletes the last character still on the screen.

Strings are immutable in Python

Immutable means "can't be changed in place". When you write result = result[:-1] or result = result + ch, Python builds a brand new string and copies all the characters into it. That copy costs O(length). The teacher mentions that in Java you'd use a StringBuilder for this, and in Python you can simply use a string. Just remember each change makes a copy. A list (our stack) doesn't have that problem: append and pop at the end are O(1).

Part A · Brute force: build the typed string and delete from its end

LeetCode 844

1The question in simple words

You get two strings, s and t. Imagine typing each one into an empty text editor, one character at a time. A # is the backspace key: it deletes the character just before the cursor (the last character on the screen). The # itself never appears on the screen. Return True if both editors end up showing the same text, else False.

Both show "ac", so the answer is True. That's the teacher's first example.

Two more from LeetCode: s = "ab##", t = "c#d#" → both become empty "" → True. And s = "a#c", t = "b" → "c" vs "b" → False.

2What the constraints tell us

• 1 ≤ s.length, t.length ≤ 200. The strings are tiny. The teacher's point: with n = 200 even an O(n²) solution is safe (200² = 40,000 steps, far below the ~10⁸ limit). So the brute force will pass. It'll just be slower, and we'll still optimise it because an interviewer will ask.
• Lengths are at least 1, so a string is never empty to start with. But the typed result can be empty (like "ab##"), and a # can come when the editor is already empty (like "#a"). Backspace on an empty editor does nothing.
• s and t contain only lowercase letters and #.
• s and t can have different lengths. Lengths before typing don't tell you anything; "ab#" (3 chars) and "a" (1 char) give the same screen.

3Intuition: just do what the editor does

The most obvious idea: actually type each string into a fresh piece of text (call it s1 for s, t1 for t). A letter → add it at the end. A # → delete the last character, if there is one. At the end, compare s1 and t1.

4Building the logic from the example

Type s = "ab#c":

1. a is a normal letter, it's safe → s1 = "a".
2. b → s1 = "ab".
3. # → delete the previous character from s1 → s1 = "a". The # itself is not added.
4. c → s1 = "ac".

Type t = "ad#c" the same way: "a" → "ad" → "a" → "ac". Now s1 == t1 → True.

Is this really O(n)? The many-# case

At first it looks like one pass, so O(n). The teacher then asks: what about something like "abcdefab###", where many # come together? Every # makes us go back and delete. With an immutable string, every delete (and every add) builds a new copy of the whole text, which is O(current length). So in the worst case this approach is O(n²). Her advice here: forget the exact time for now, first get any working solution.

5Approach steps

1. Write a helper build(text) that returns what the editor shows.
2. Inside: start with result = "". For each character: if it's # and result isn't empty, cut off the last character. Otherwise (a letter), add it at the end.
3. Return build(s) == build(t).

6Code (Python)

class Solution:
    def backspaceCompare(self, s, t):
        return self.build(s) == self.build(t)

    def build(self, text):
        result = ""
        for ch in text:
            if ch == "#":
                if len(result) > 0:          # backspace on empty does nothing
                    result = result[:-1]     # new string without the last char
            else:
                result = result + ch         # new string with ch at the end
        return result

7Code line by line

8Dry run

s = "ab#c", t = "ad#c".

"ac" == "ac" → True ✓

9Complexity & remember

• Time O(n²) in the worst case in Python, because every add or delete copies the string. (With Java's StringBuilder, or a list, each step would be O(1) and the whole thing O(n).) Here n = len(s) + len(t).
• Space O(n): the two built strings s1 and t1.

Part B · Stack: the cleaner way to undo

1The question (same as Part A)

Same question: type both strings with # as backspace, and compare the screens. Only the tool changes.

2What the constraints tell us

Same as Part A: n ≤ 200, so speed isn't the problem. The goal of this part is a cleaner idea, not a faster one. The teacher says it openly: the stack doesn't reduce the time or space, but it makes the solution simpler.

3Intuition: "go forward, then come back to delete" is a stack

The teacher points out a feeling we've had in earlier problems: we're moving forward, and suddenly something (here a #) tells us to go back and change the latest thing we saw. With one # we go back once; with many #s we go back many times. Whenever "move forward, but sometimes undo the most recent thing" appears, think of a stack. The "go back and delete" step is just a pop.

• A letter → push it.
• A # → pop the top (the latest letter still alive), but only if the stack isn't empty.

At the end, the stack holds exactly the characters left on the screen, bottom to top = left to right.

4Building the logic from the example

For s = "ab#c": push a, push b, # → pop b, push c. Stack = [a, c]. For t = "ad#c": push a, push d, # → pop d, push c. Stack = [a, c]. Same → True.

Nicer than Part A: we don't think about strings, copies or builders while scanning. We only push and pop.

5Approach steps

1. Helper build(text): make an empty stack.
2. For each character: if it's #, pop if the stack is non-empty. Otherwise push the character.
3. Turn the stack into a string and return it.
4. Main function: return build(s) == build(t).

6Code (Python)

class Solution:
    def backspaceCompare(self, s, t):
        return self.build(s) == self.build(t)

    def build(self, text):
        stack = []
        for ch in text:
            if ch == "#":
                if stack:              # something to delete?
                    stack.pop()        # undo the latest character
            else:
                stack.append(ch)       # a normal character stays (for now)
        return "".join(stack)          # bottom..top = left..right

7Code line by line

8Dry run (stack after every step)

The teacher's longer example: s = "ab#cd##f#g", t = "ab#g". Stack drawn left = bottom, right = top.

The top is in red. Two # in a row simply pop twice: first d, then c, which became the top after d left.

For t = "ab#g": push a, push b, pop b, push g → [a, g] → "ag". Both "ag" → True ✓

9Complexity & remember

• Time O(n): each character is pushed at most once and popped at most once (O(1) each), plus O(n) to join the result.
• Space O(n): the stack, plus the string we build from it. The teacher calls this out: we're still using extra space (a stack and a builder for each string). That's why it ran slower on LeetCode, and since n is so small, an interviewer will likely push you to remove the extra space.

Part C · Optimal: two pointers from the right, O(1) space

1The question (same), the new goal

Same question. The new goal: no stack, no new strings. Only a few integer variables, so O(1) extra space, and every character looked at exactly once.

2What the constraints tell us

• n ≤ 200 for each string → time was never the issue. The teacher says interviewers may still want this version, because of the space. She stresses that even though it's an "Easy" problem, this optimisation uses a different logic.
• The lengths can differ, so the two pointers can run out at different times. We'll need a condition for that.

3Intuition: walk backwards, so you know what to skip

The teacher's key observation: a backspace only ever affects characters on its LEFT. When we walk left to right, we add a character and only later learn it must be removed, so we do the work twice (add, then undo), roughly 2n steps. If we walk right to left, we meet the # before the characters it deletes. So we already know "the next character I meet should be skipped", and we never add it in the first place.

Picture it: you read both strings from the end. You carry a small counter skip in your pocket. Each # adds 1 to it. Each letter you meet while skip > 0 is a deleted letter: throw it away and take 1 off skip. When you reach a letter with skip = 0, that letter really is on the screen. Stop there.

Do this in both strings. Now you're standing on the last surviving character of each one. If they differ, the screens differ → False right away. If they're the same, step both pointers left and repeat for the next surviving character.

4Building the conditions

Condition 1: the skipping loop (one for s, one for t)

Starting from the pointer i in s, keep moving left while one of these is true:

• s[i] == '#' → one more backspace waiting: skip_s += 1, i -= 1.
• a letter but skip_s > 0 → this letter was deleted: skip_s -= 1, i -= 1.
• a letter and skip_s == 0 → a real character. Stop (break).

Same for t with j and skip_t. Note: skip is a count, not a True/False, because several # can pile up. The teacher's example: three # after "c" → skip becomes 3 → the next three letters are all thrown away.

Condition 2: compare the survivors

• Both pointers valid (i >= 0 and j >= 0) and s[i] != t[j] → the screens differ at this position → return False right away.
• Exactly one pointer ran out (one is ≥ 0, the other is < 0) → one screen still has a character, the other has none left → different lengths → return False. The teacher's example: s = "ab#c" but t without the "a": t's pointer goes negative while s's still points at a real character.
• Otherwise (same character) → step both pointers left: i -= 1, j -= 1, and repeat.

5Approach steps

1. i = len(s) - 1, j = len(t) - 1, skip_s = skip_t = 0.
2. While i >= 0 or j >= 0:
3. Move i left past every # and every letter they delete. Stop on a surviving letter (or when i < 0).
4. Do the same for j in t.
5. Both valid and different → False. Exactly one valid → False.
6. Otherwise i -= 1, j -= 1.
7. After the loop → True.

6Code (Python)

class Solution:
    def backspaceCompare(self, s, t):
        i = len(s) - 1
        j = len(t) - 1
        skip_s = 0                    # how many # are waiting in s
        skip_t = 0                    # how many # are waiting in t

        while i >= 0 or j >= 0:
            # find the next surviving character in s
            while i >= 0:
                if s[i] == "#":
                    skip_s += 1
                    i -= 1
                elif skip_s > 0:     # this letter was backspaced
                    skip_s -= 1
                    i -= 1
                else:
                    break             # s[i] is really on the screen
            # find the next surviving character in t
            while j >= 0:
                if t[j] == "#":
                    skip_t += 1
                    j -= 1
                elif skip_t > 0:
                    skip_t -= 1
                    j -= 1
                else:
                    break

            if i >= 0 and j >= 0:
                if s[i] != t[j]:      # survivors differ
                    return False
            elif i >= 0 or j >= 0:    # only one string has a survivor
                return False

            i -= 1
            j -= 1

        return True

7Code line by line

8Dry run (the teacher's example)

s = "ab#cd##f#g", t = "ab#g" (both type to "ag"). The pointers start at the last index.

Notice what the teacher points out in her narration: at one moment the pointers sit on f in s and b in t. A naive compare would say "different". But both have a # right after them, so both are skipped and never compared. That's the whole point of skipping first.

A False example: s = "ab", t = "b".

1. Round 1: i stops at 'b' (index 1), j stops at 'b' (index 0). Same → i = 0, j = −1.
2. Round 2: the loop runs because i ≥ 0. i stops at 'a'. j is already −1. One valid, one not → return False ✓

9Complexity & remember

• Time O(n + m) (n = len(s), m = len(t)): every index of each string is visited once, by either the inner loop or the outer loop. The teacher counts it as 200 + 200 = 400 steps at most. It's still linear like the stack, but we never "add then undo", so there's no wasted double work.
• Space O(1): only i, j, skip_s, skip_t. No stack, no new string. This was the fastest of the three on LeetCode.

The teacher's closing lesson: even when a problem is clearly from the stack family, there can be a simpler optimised idea, and spotting it comes with practice. In the beginning, thinking of the stack is already good enough.

Part D · Revision page

s = Solution()
print(s.backspaceCompare("ab#c", "ad#c"))         # True
print(s.backspaceCompare("ab##", "c#d#"))         # True
print(s.backspaceCompare("a#c", "b"))             # False
print(s.backspaceCompare("ab#cd##f#g", "ab#g"))   # True
print(s.backspaceCompare("ab", "b"))              # False
print(s.backspaceCompare("#", "a#"))              # True

Based on this video: Backspace String Compare | Stack simulation & undo pattern