Stack · LC #844
Backspace String Compare
Compare two strings after processing backspace characters (#), using a stack to simulate the final typed text. Includes an O(1)-space two-pointer follow-up.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two strings `s` and `t` where the character `#` represents a backspace, return `true` if they are equal after processing all backspaces. Note: pressing backspace on an empty text does nothing.
Sample I/O
Input: s = "ab#c", t = "ad#c"
Output: true (both become "ac")
Input: s = "a#c", t = "b"
Output: false ("c" vs "b")
Input: s = "a##c", t = "#a#c"
Output: true (both become "c")Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
A stack perfectly models text editing: normal characters are pushed, and backspace pops the last character (or does nothing on empty). After processing both strings, compare the resulting stacks character by character.
Core Concept
Process each string with a helper that pushes non-`#` characters and pops on `#` (ignoring `#` when the stack is empty). Convert both final stacks to strings and compare. The O(1)-space alternative scans both strings from right to left, using a skip counter to track pending backspaces, and compares characters one at a time without materializing the result.
When to use
Simulating sequential state changes where any step can undo the previous step. Common in text-editing, command-history, and undo-chain problems.
When NOT to use
When backspaces can reference positions beyond the immediately preceding character (random-access undo), which requires a different structure.
Key Insights
What to Know Cold
- Backspace on empty string is a no-op - always guard with `if (!stack.isEmpty())` before popping.
- The two-pointer O(1)-space approach scans right-to-left; each `#` increments a skip counter, and skip > 0 consumes non-`#` characters.
- Multiple consecutive backspaces are handled naturally: each `#` pops one character (stack) or increments skip by 1 (two-pointer).
- The strings can have different lengths yet still be equal after processing (e.g., `"a##c"` and `"c"`).
- Converting the final stack to a comparable type matters in Java - use `stack.toString()` consistently or build a String.
1 example
Worked Examples
O(1)-space two-pointer approach
Compare `"ab#c"` and `"ad#c"` without building intermediate strings.
Scan both strings right-to-left. Maintain a skip counter per string. When `#` is seen, increment skip. When a normal char is seen and skip > 0, decrement skip (consumed). When skip = 0 compare the characters; mismatch → false.
function backspaceCompareO1(s: string, t: string): boolean {
let i = s.length - 1, j = t.length - 1;
let skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && (s[i] === '#' || skipS > 0)) {
if (s[i] === '#') skipS++; else skipS--;
i--;
}
while (j >= 0 && (t[j] === '#' || skipT > 0)) {
if (t[j] === '#') skipT++; else skipT--;
j--;
}
if (i >= 0 && j >= 0 && s[i] !== t[j]) return false;
if ((i >= 0) !== (j >= 0)) return false;
i--; j--;
}
return true;
}Output: true
Demonstrates the O(1)-space optimization that interviewers explicitly ask for - reduces stack allocation to two integer counters.