844 - Backspace String Compare

Difficulty: Easy | Pattern: Two Pointers | Company tags: Amazon, Google, Facebook

Problem Statement

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue to be empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true  (both become "ac")

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true  (both become "")

Example 3:

Input: s = "a##c", t = "#a#c"
Output: true  (both become "c")

Approach 1: Stack — O(n+m), O(n+m)

Algorithm Flow

def backspaceCompare(s: str, t: str) -> bool:
    def process(string):
        stack = []
        for ch in string:
            if ch == '#':
                if stack:
                    stack.pop()
            else:
                stack.append(ch)
        return stack
    
    return process(s) == process(t)

Approach 2: Two Pointers from End — O(n+m), O(1)

Key insight: Process both strings from right to left, skipping characters consumed by backspaces. Compare the next valid characters.

def backspaceCompare(s: str, t: str) -> bool:
    i, j = len(s) - 1, len(t) - 1
    skip_s = skip_t = 0
    
    while i >= 0 or j >= 0:
        while i >= 0:
            if s[i] == '#':
                skip_s += 1
                i -= 1
            elif skip_s > 0:
                skip_s -= 1
                i -= 1
            else:
                break
        
        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 and s[i] != t[j]:
            return False
        if (i >= 0) != (j >= 0):
            return False
        
        i -= 1
        j -= 1
    
    return True

Dry Run

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

Stack approach:

• s: a,b,#(pop b),c → ['a','c']
• t: a,d,#(pop d),c → ['a','c']
• Equal → True ✓

Edge Cases

• All backspaces on empty string → empty result (backspace ignored)
• More # than letters → empty
• "#" == "" → True (empty)

Complexity

Approach	Time	Space
Stack	O(n+m)	O(n+m)
Two Pointers	O(n+m)	O(1)

Key Terms

Term	Definition
Stack	LIFO structure used to build the "typed" text, popping on '#'.
Two pointers	Traversing s and t from the end simultaneously, comparing only the surviving characters.
Skip counter	A counter tracking how many upcoming characters (moving right-to-left) must be discarded due to pending backspaces.
Lazy deletion	Instead of physically building a result string, skip-counting simulates deletion in O(1) extra space.
In-place simulation	Processing the input directly (from the back) without allocating a new data structure.

FAQ

Q: Can this be solved without extra space? A: Yes — the two-pointer approach from the end of both strings uses O(1) extra space by tracking a skip counter instead of building a stack.

Q: What if the input is empty, or one string is empty and the other isn't? A: An empty string trivially "types" to itself. If one string reduces to "" after backspaces and the other doesn't, the two-pointer method correctly returns False when one pointer runs out before the other finds a valid character.

Q: What if backspacing an empty text should error instead of being a no-op? A: The problem explicitly states backspacing empty text keeps it empty; if that constraint were relaxed to raise an error, you'd need to track whether a pop was attempted on an empty stack and short-circuit.

Q: How would this change if '#' could also mean "delete forward" (like the Delete key) instead of backspace? A: You'd need a different model entirely — forward deletion depends on cursor position, so a simple stack/two-pointer approach wouldn't directly apply; you'd likely simulate an actual cursor over a mutable buffer.

Q: What's the follow-up interviewers usually ask? A: "Can you do it in O(1) space?" (leads to the two-pointer solution), and sometimes "What if there are multiple special characters like '#' for backspace and '*' for delete-all?"

Quick Revision

• Pattern: two pointers scanning from the end, with a stack-based approach as the simpler baseline.
• Stack approach: push normal chars, pop on '#' (no-op if stack empty); compare final stacks.
• Two-pointer approach: walk both strings backward, using a skip counter to swallow characters consumed by pending '#'.
• A character survives once skip == 0 and the current char isn't '#'.
• Compare survivors position by position; mismatch or one string running out early (while the other still has one) means False.
• Stack approach: O(n+m) time, O(n+m) space. Two-pointer approach: O(n+m) time, O(1) space.
• Edge cases: all backspaces, more '#' than letters, one string empties out completely.
• Interview tip: mention the O(1) space version as the optimized follow-up after the stack solution.

Related Problems

• 71 - Simplify Path (LeetCode) — same "stack that pops on a special token" pattern applied to path segments.
• 20 - Valid Parentheses (LeetCode) — foundational stack-based matching/removal pattern this problem builds on.