Backspace String Compare
Two strings s and t record keystrokes typed into an initially empty text box. A lowercase letter types that letter, and the character '#' is a backspace that deletes the most recently typed letter still in the box. Pressing backspace when the box is empty does nothing.
Return true if both keystroke sequences leave exactly the same text in the box, and false otherwise.
Building both final strings is easy; try to also find a solution that uses only O(1) extra memory.
Example 1
Example 2
Example 3
Constraints
1 <= s.length, t.length <= 104sandtcontain only lowercase English letters and'#'.
Pattern Path · Two Pointers · problem 16 of 169
#. That costs O(n) memory. Can you avoid storing the results?Start simple
Simulate both strings with a stack and compare the results: O(n + m) time but O(n + m) extra space.
The key idea
Reading left to right, you cannot tell whether a letter survives, because a later # might delete it. Reading right to left removes that uncertainty: by the time you reach a letter, you have already seen every backspace that could delete it.
So walk a pointer backwards through each string while keeping a skip counter. A # increases skip; a letter with skip > 0 is deleted, so decrease skip and move on; a letter with skip == 0 is the next surviving character (counting from the end).
Advance both pointers to their next surviving characters and compare them. If one string runs out while the other still has a survivor, the texts differ in length. If the characters differ, the texts differ. If both run out together, every surviving character matched and the answer is true.
Each pointer only moves left, so the total work is linear, and we store nothing but two indices and two counters.
Complexity
- Time:
O(n + m) - Space:
O(1)
Python
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def next_survivor(text, i):
"""Index of the next character at or before i that is not deleted, or -1."""
skip = 0
while i >= 0:
if text[i] == '#':
skip += 1
elif skip > 0:
skip -= 1
else:
break
i -= 1
return i
i, j = len(s) - 1, len(t) - 1
while True:
i = next_survivor(s, i)
j = next_survivor(t, j)
if i < 0 or j < 0:
return i < 0 and j < 0 # both must run out together
if s[i] != t[j]:
return False
i -= 1
j -= 1JavaScript
var backspaceCompare = function(s, t) {
// Index of the next character at or before i that is not deleted, or -1.
const nextSurvivor = (text, i) => {
let skip = 0;
while (i >= 0) {
if (text[i] === '#') skip++;
else if (skip > 0) skip--;
else break;
i--;
}
return i;
};
let i = s.length - 1;
let j = t.length - 1;
while (true) {
i = nextSurvivor(s, i);
j = nextSurvivor(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // both must run out together
if (s[i] !== t[j]) return false;
i--;
j--;
}
};What the interviewer is checking
The stack version is the warm-up; the interviewer is looking for the insight that scanning backwards lets you decide each character's fate immediately, giving O(1) space.
Mistakes to avoid
- Letting a backspace on an empty box go negative or crash a pop on an empty stack.
- Resetting the skip counter too early, so a run like
"ab##"deletes only one letter. - Stopping when one string is exhausted without checking whether the other still has surviving characters.
Follow-ups to expect
- What if the editor also supports an undo key? (Stack of operations.)
- What if the input arrives as a stream? (Stack-based simulation instead.)
- Return the final text itself. (Stack, or write-pointer in place.)
In real software
Terminal line editors and keystroke-replay tools reconstruct the final input from raw key events, and comparing two edit logs without materialising them is useful when the logs are large.