Backspace String Compare: Stack and Two-Pointer Solutions

You are given two strings where # means backspace. After processing all the backspaces, do the two strings end up equal? This is LeetCode 844: Backspace String Compare, rated easy. There are two clean ways to solve it, and the optimal one uses no extra memory at all.

The problem

Given two strings s and t, return True if they are equal after processing all backspace characters. The # character deletes the character before it. If there is nothing to delete, the # is simply ignored.

Input:  s = "ab#c", t = "ad#c"
Output: True  # both become "ac"

Input:  s = "ab##", t = "c#d#"
Output: True  # both become ""

Input:  s = "a#c", t = "b"
Output: False  # "c" != "b"

Approach 1: Stack-based (simpler)

The most natural way to think about this: simulate the typing. Walk through each string character by character. If you see a regular character, push it onto a stack. If you see #, pop the top (if anything is there). When you finish, whatever remains in the stack is the final string.

Do this for both strings and compare the results.

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

    return process(s) == process(t)

This is clean and easy to get right. The process helper builds the final string by simulating every keystroke. If char is # and the stack is non-empty, we pop. Otherwise we push. At the end, we join the stack into a string and compare.

Approach 2: Two pointers with O(1) space (optimal)

The follow-up question on LeetCode asks: can you solve it in O(1) space? You can, by working backwards through both strings simultaneously.

The key insight is that a # character only affects characters to its left, never to its right. So if you scan from right to left, you can count how many characters to skip without needing to store the processed string at all.

Use two pointers, i starting at the end of s and j starting at the end of t. For each pointer, before comparing:

1. If the current character is #, increment a skip counter and move left.
2. If the skip counter is greater than 0, decrement it and move left (this character is deleted).
3. Otherwise, the character is valid. Stop and compare.

After both pointers have found their next valid character, compare them. If they differ, return False. If one pointer is exhausted and the other is not, return False. Otherwise, move both pointers left and repeat.

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

The inner while loops for i and j each handle the "find next valid character" logic. They keep moving left as long as they encounter backspaces or need to skip characters. Once both pointers settle on valid characters (or run out of string), the outer loop compares them.

The check (i >= 0) != (j >= 0) catches the case where one string still has valid characters but the other is exhausted. That means the strings have different lengths after processing, so they cannot be equal.

Step-by-step walkthrough

Trace through s = "ab#c" and t = "ad#c" using the two-pointer approach, working from right to left.

Both pointers reached the end together, and every comparison matched. The strings are equal after processing backspaces.

Complexity analysis

Where n is the length of s and m is the length of t.

Time: Both approaches process every character in both strings exactly once. The two-pointer version has nested loops, but each character is visited at most twice (once to count/skip, once to compare), so it is still O(n + m).

Space: The stack approach stores up to all characters from both strings. The two-pointer approach uses only a handful of integer variables regardless of input size.

The building blocks

Stack-based string processing

The process helper is a general pattern: walk through a sequence, and use a stack to build a result while handling deletions or undo operations. This same structure appears whenever you need to simulate editing operations on a string or evaluate expressions with cancellation.

def process(string: str) -> str:
    stack = []
    for char in string:
        if char == '#':
            if stack:
                stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Reverse iteration with a skip counter

The two-pointer approach introduces a pattern where you iterate backwards and maintain a counter for "how many characters to skip." This avoids building the processed string entirely. The counter acts as a lightweight substitute for the stack, working because backspaces only affect characters to their left.

while i >= 0:
    if s[i] == '#':
        skip_s += 1
        i -= 1
    elif skip_s > 0:
        skip_s -= 1
        i -= 1
    else:
        break

This "skip counter" pattern is useful whenever you need to process deletions or cancellations from right to left without extra space.

Edge cases

• All backspaces, empty result: s = "ab##", t = "c#d#". Both reduce to "". The stack approach produces two empty strings. The two-pointer approach has both pointers exhaust their strings without finding any valid characters. Return True.
• Consecutive backspaces: s = "abc###". Each # deletes one character working left. The stack pops three times, leaving an empty result. The skip counter accumulates to 3 and skips all three characters.
• Backspace with nothing to delete: s = "#a#b". The first # has nothing to delete (stack is empty, so we skip the pop). Then a is pushed and immediately deleted by the next #. Only b remains.
• No backspaces at all: s = "abc", t = "abc". Both approaches just compare the strings directly. The skip counters stay at 0.
• Single character vs empty: s = "a", t = "a#". After processing, s = "a" and t = "". The two-pointer approach catches this with the (i >= 0) != (j >= 0) check.

From understanding to recall

The stack solution is intuitive once you see it. The two-pointer solution is elegant but has more moving parts: the inner while loops, the skip counters, the two separate end-of-string checks. Under time pressure, it is easy to mix up the order of conditions or forget the asymmetric length check.

The way to make both approaches automatic is to practice writing them from scratch. Trace through "ab##" vs "c#d#" by hand. Rebuild the skip-counter logic without looking. After a few spaced repetition cycles, the nested while-loop structure and the comparison checks flow naturally.

This problem is a great example of how the same result can come from two completely different techniques. The stack approach builds and compares. The two-pointer approach avoids building anything. Knowing both gives you flexibility in interviews, especially when the follow-up asks about space optimization.

Related posts

• Valid Parentheses - Another stack-based matching problem where you process characters and validate structure
• Evaluate Reverse Polish Notation - Stack-based expression evaluation with a similar push/process pattern
• Remove Duplicates from Sorted Array - Two-pointer technique for in-place array processing