Backspace String Compare Backwards in Constant Space

If you interview at Google, Meta, Oracle, expect some version of "Backspace String Compare". It is rated Easy, and it falls squarely into the Two Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 10 of 12 in the Two Pointers arc.

The Problem

Given strings s and t, return True if they are equal when typed into empty text editors, where "#" means backspace. The stack simulation is easy; the follow-up — O(n) time and O(1) space — is the actual Google question.

Input:  s = "ab#c", t = "ad#c"
Output: True
Both type out as "ac".

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

A backspace erases leftward, so its effect is only resolvable when scanning right to left: count pending backspaces, skip that many characters. Reverse iteration with two synchronized pointers is what upgrades the stack solution to constant space.

The Approach

Walk both strings from the end with one pointer each. A helper advances a pointer to its next surviving character: on '#' increment a skip counter, on a letter consume a skip or stop. Compare surviving characters pairwise; any mismatch — including one string surviving longer — is a fail.

Structure the helper as its own function. Interviewers grade the decomposition here almost as much as the algorithm.

Python Solution

def backspace_compare(s: str, t: str) -> bool:
    """True if s and t are equal after applying '#' backspaces."""

    def next_alive(string: str, i: int) -> int:
        """Index of the next surviving char at or before i, else -1."""
        skip = 0
        while i >= 0:
            if string[i] == "#":
                skip += 1
            elif skip > 0:
                skip -= 1
            else:
                return i
            i -= 1
        return -1

    i, j = len(s) - 1, len(t) - 1
    while i >= 0 or j >= 0:
        i = next_alive(s, i)
        j = next_alive(t, j)
        if i >= 0 and j >= 0:
            if s[i] != t[j]:
                return False
        elif i >= 0 or j >= 0:
            return False        # one string has extra surviving chars
        i -= 1
        j -= 1
    return True

Complexity

• Time: O(n + m) — each character of each string is visited once
• Space: O(1) — two indices and two skip counters — no stacks

Interview Tips and Follow-Ups

• Lead with the stack version in 30 seconds, state its O(n) space, then pivot backwards — that arc is what earns the follow-up points.
• Backspaces on an empty buffer ("#a" style inputs) are the edge case the helper's skip logic must absorb.
• Same backwards trick powers Merge Sorted Array (LeetCode 88) — filling from the tail avoids overwrites.

That wraps part 10 of the Two Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.