Backspace String Compare

The problem. Two strings s and t are typed into empty text editors, where # means backspace. Return true if both editors end up showing the same text. A backspace on an empty editor does nothing.

Example

s = "ab#c",  t = "ad#c"   ->  true    (both "ac")
s = "ab##",  t = "c#d#"   ->  true    (both empty)
s = "a#c",   t = "b"      ->  false   ("c" vs "b")

The pattern: stack

A stack fits whenever the newest character is the one that can be cancelled, matched or undone: backspaces erase the last letter typed, a ) closes the most recent (, a letter cancels an equal letter right before it. Push characters as you read them; when one cancels, pop the top. Whatever is left on the stack is the result.

The Stack course covers the basics, Valid Parentheses and Decode String. This chapter applies the same idea to three string-editing questions, from a direct use to one where the stack stores indexes to delete.

1. Replay the typing on a stack

Build the final text of each string with a stack (an array, a list, a StringBuilder or a std::string used as a stack), then compare the two.

1function backspaceCompare(s, t) {2  const build = (str) => {3    const stack = [];4    for (const ch of str) {5      if (ch === "#") stack.pop();            // backspace: remove the last character typed6      else stack.push(ch);                    // (popping an empty stack does nothing)7    }8    return stack.join("");9  };10  return build(s) === build(t);11}

Time O(n + m), space O(n + m). Every character is pushed or popped once, and the two stacks can hold every letter.

2. Two pointers from the end, O(1) space

The classic follow-up asks for O(1) extra space. Read both strings backwards: then a # is seen before the letter it erases, so just count pending backspaces and skip that many letters. Compare the surviving characters one pair at a time.

1function backspaceCompare(s, t) {2  let i = s.length - 1, j = t.length - 1;3  let skipS = 0, skipT = 0;                   // backspaces still to apply4  while (i >= 0 || j >= 0) {5    while (i >= 0) {                          // find the next character of s that survives6      if (s[i] === "#") { skipS++; i--; }7      else if (skipS > 0) { skipS--; i--; }8      else break;9    }10    while (j >= 0) {                          // ...and the next one of t11      if (t[j] === "#") { skipT++; j--; }12      else if (skipT > 0) { skipT--; j--; }13      else break;14    }15    if (i >= 0 && j >= 0 && s[i] !== t[j]) return false;   // different surviving characters16    if ((i >= 0) !== (j >= 0)) return false;               // one string has more left17    i--;18    j--;19  }20  return true;21}

Time O(n + m), space O(1). Each pointer only moves left, so every character is passed once.

Comparing the approaches

Lead with the stack — it states the problem directly. Then offer the backwards scan for O(1) space: reading in reverse turns "undo the past" into "skip the future", which needs only a counter.

Edge cases to test

Variations