Backspace String Compare — Stack and O(1) Space Two-Pointer

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.

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Input:  s = "ab#c", t = "ad#c"
Output: true
Explanation: Both become "ac" after applying backspaces.

Input:  s = "ab##", t = "c#d#"
Output: true
Explanation: Both become "" after applying backspaces.

Input:  s = "a#c", t = "b"
Output: false
Explanation: s becomes "c", t becomes "b". Not equal.

Why This Problem Matters#

LC 844 is an easy-medium problem that tests two different techniques: a straightforward stack simulation (O(n) space) and a clever two-pointer scan from the right (O(1) space). The two-pointer approach is the "optimal" solution that interviewers at Amazon, Microsoft, and Google are looking for when they ask the follow-up "can you do it in O(1) extra space?"

The backspace problem models real text editing. Any time you process a stream of characters with possible undo-last operations, this pattern applies — terminal input processing, command-line editing (backspace), and keystroke logging all use variations of this logic.

Understanding both approaches demonstrates algorithmic range: knowing when a simple stack works and when you can eliminate the space overhead with a smarter scan order.

The Core Insight#

Stack approach (O(n) space): Simulate the typing. When you see a regular character, push it. When you see '#', pop (if the stack is not empty). The final stack contents are the resulting string. Compare the two resulting strings.

Two-pointer approach (O(1) space): Scanning left to right, you have to "look ahead" to know which characters survive. Scanning right to left, the relationship is local — a '#' cancels the next non-'#' character to the left. Use skip counters to track how many characters to skip, and compare character by character once each pointer settles on a surviving character.

The two-pointer trick is powerful: whenever the natural processing order is left-to-right but backspace-like operations cancel forward from the right, scanning right-to-left makes the problem local and eliminates the need for auxiliary storage.

Visual Dry Run#

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

Stack simulation for s:

• 'a' → push → ['a']
• 'b' → push → ['a','b']
• '#' → pop → ['a']
• 'c' → push → ['a','c']
• Result: "ac"

Stack simulation for t:

• 'a' → push → ['a']
• 'd' → push → ['a','d']
• '#' → pop → ['a']
• 'c' → push → ['a','c']
• Result: "ac"

"ac" == "ac" → return true.

Two-pointer, scanning from right:

→ return true.

Solution (Optimal)#

# Python — O(1) space two-pointer from right
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:
        # Advance i to the next surviving character in s
        while i >= 0:
            if s[i] == '#':
                skip_s += 1
                i -= 1
            elif skip_s > 0:
                skip_s -= 1  # this character is erased by a previous '#'
                i -= 1
            else:
                break        # s[i] is a surviving character
 
        # Advance j to 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
 
        # Both pointers are now on surviving characters (or exhausted)
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False  # surviving characters differ
        elif i >= 0 or j >= 0:
            return False      # one string has more surviving characters
 
        i -= 1
        j -= 1
 
    return True
 
 
# Python — stack simulation, O(n) space, simpler to reason about
def backspaceCompareStack(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)

// JavaScript — O(1) space two-pointer from right
function backspaceCompare(s, t) {
    let i = s.length - 1, j = t.length - 1;
    let skipS = 0, skipT = 0;
 
    while (i >= 0 || j >= 0) {
        // Find next surviving char in s
        while (i >= 0) {
            if (s[i] === '#') { skipS++; i--; }
            else if (skipS > 0) { skipS--; i--; }
            else break;
        }
        // Find next surviving char in t
        while (j >= 0) {
            if (t[j] === '#') { skipT++; j--; }
            else if (skipT > 0) { skipT--; j--; }
            else break;
        }
 
        if (i >= 0 && j >= 0 && s[i] !== t[j]) return false;
        if ((i >= 0) !== (j >= 0)) return false;
 
        i--;
        j--;
    }
 
    return true;
}

Complexity:

Common Mistakes#

1. Not handling consecutive backspaces. A string like "###" should produce an empty string. The skip counter handles this: each '#' increments skip, and each non-'#' decrements skip if positive — multiple backspaces are handled naturally.

2. Not guarding against empty stack in the stack simulation. A leading '#' like "#a" has no character to delete. Always check if stack: before stack.pop().

3. Off-by-one in the two-pointer approach. After comparing two surviving characters, you must decrement both i and j to move to the next pair. Forgetting to decrement after the comparison causes an infinite loop.

4. Comparing after both pointers exhaust at different times. If one string has more surviving characters than the other, the pointers exhaust at different positions. The check (i >= 0) != (j >= 0) catches this case — one is in bounds while the other is not.

5. Converting to strings for comparison in the two-pointer approach. Some candidates process the skip counters but then join the surviving characters — this negates the O(1) space benefit.

Interview Tips#

• Start with the stack approach: "The natural solution is O(n) space — simulate with a stack, pop on '#', compare results." This earns partial credit and shows you can code cleanly.
• Then offer the follow-up: "The O(1) space solution scans right to left with skip counters. Right-to-left works because '#' cancels the character immediately to its left."
• Trace through "a##" (empty result) to show you handle consecutive backspaces correctly.
• The two-pointer inner while loops are the tricky part — each inner loop finds the next surviving character, consuming all backspaces and cancelled characters.

Follow-up Questions#

1. O(1) space for all n characters removed? The two-pointer handles this — "abc###" results in zero surviving characters, and both pointers exhaust at the start.
2. What if ^ means delete all characters up to the previous space? Harder variant — use a stack that tracks word boundaries.
3. What if backspace can only delete the most recent character (not backspace over another backspace)? The current solution handles this because each '#' increments skip by 1 regardless.
4. Return the resulting string instead of comparing. Use the stack simulation directly and return ''.join(stack).
5. Handle multiple types of control characters? Generalize the skip logic — each control character type gets its own counter or stack layer.

Key Takeaways#

• Stack simulation is the natural O(n) space solution: push characters, pop on '#', compare the resulting stacks.
• Two-pointer from right achieves O(1) space: scan backwards with skip counters; each '#' increments skip, each non-'#' decrements skip if positive, otherwise it is a surviving character.
• Scanning right to left converts a forward-looking dependency ('#' affects the character before it) into a local decision at each index.
• Guard for empty stack before popping in the simulation approach, and symmetric exhaustion in the two-pointer approach.
• This problem is a microcosm of the "process with potential undo" pattern — recognizing that pattern immediately is the key interview signal.
• The O(1) space solution is the expected follow-up at FAANG; always offer it after demonstrating the simpler stack version.