Backspace String Compare (LeetCode 844)

The problem

You get two strings s and t that were typed into a text editor. The character # means backspace: it deletes the character before it, if there is one. Return True if both strings end up the same after all the backspaces.

Input:  s = "abc#d", t = "abzz##d"
Output: True

In s the # erases c, leaving "abd". In t the two #s erase both zs, also leaving "abd".

How to think about it

Start with brute force. Simulate the editor with a stack: push each character, pop on #. Build the final text for both strings and compare. That’s O(n + m) time and O(n + m) space, and it’s a perfectly good first answer. The follow-up is: do it in O(1) space.

Why left-to-right is awkward. Scanning forwards, you don’t know whether the character you’re looking at will survive. A # later on might delete it. So you’d have to buffer characters, which is what the stack does.

The key insight: scan from the right. Going backwards, a # only affects characters you haven’t reached yet. So keep a counter skip of pending backspaces. When you see #, add one to skip. When you see a normal character and skip > 0, it’s erased: decrease skip and move on. Otherwise, it’s a character that definitely survives. Do this for both strings in lockstep and compare surviving characters one pair at a time.

Which pattern is this? Two pointers, one per string, both moving right to left. The tell is “compare two sequences after edits, in constant space”.

Approach

1. Write a helper nxt(st, i) that moves i left past every erased character and returns the index of the next surviving one (or -1).
2. Start i and j at the last index of s and t.
3. While either pointer is still in range, jump both to their next survivor.
4. If both exist and differ, return False. If only one exists, the lengths differ, so return False.
5. Otherwise step both left and repeat. If you run out together, return True.

Solution

def backspace_compare(s, t):
    def nxt(st, i):
        skip = 0                                   # pending backspaces
        while i >= 0:
            if st[i] == '#': skip += 1; i -= 1
            elif skip:        skip -= 1; i -= 1   # this char gets erased
            else: break                            # survivor found
        return i
    i, j = len(s)-1, len(t)-1
    while i >= 0 or j >= 0:
        i = nxt(s, i); j = nxt(t, j)
        if i >= 0 and j >= 0:
            if s[i] != t[j]: return False
        elif i >= 0 or j >= 0:                     # one string ran out early
            return False
        i -= 1; j -= 1
    return True
# backspace_compare("ab#c", "ad#c") -> True

Dry run

On s = "abc#d" and t = "abzz##d":

After round 3 both pointers step to -1, the loop ends, and the answer is True.

Complexity

• Time: O(n + m). Each pointer only moves left, and every character is passed over once.
• Space: O(1). A couple of indices and a skip counter per string. No new strings are built.

Edge cases and pitfalls

• Backspace on an empty editor ("#a") does nothing. The right-to-left scan handles this naturally: a leftover skip at index -1 is simply ignored.
• Both strings erase to empty ("a#" vs "b#"): both pointers reach -1 together, so True.
• Different survivor counts ("a" vs "aa"): one pointer runs out first, which the elif catches.
• Resetting skip per survivor. Each call to nxt starts with skip = 0. That’s correct, because all pending backspaces have been spent by the time a survivor is found.
• Comparing raw lengths is wrong: "ab#" and "a" have different lengths but the same result.

Related problems

• Valid Parentheses (LeetCode 20): the stack-based way of thinking that the brute force here uses.
• Valid Palindrome (LeetCode 125): two pointers that skip characters that don’t count.
• Remove K Digits (LeetCode 402): another problem about which characters survive deletions.