Backspace String Compare
Compare two strings after applying backspace edits, with the catch that the O(1) space version uses two pointers walking from the end.
By @oliviafoster
February 3, 2026
·
Updated May 20, 2026
188 views
5
4.5 (13)
Hit this on a phone screen at a fintech mid-stage in 2024, and the interviewer's follow-up was the part that tripped me up: solve it without building two new strings. The stack version is the obvious read of the problem, but the two-pointer scan from the end is the version that gets the senior signal.
Backspace String Compare
Given two strings s and t, return true if they are equal after each is processed as a sequence of typed characters and backspace edits, otherwise return false. The character '#' represents a backspace: when typed, it removes the previously typed character (if any). A backspace on an empty buffer is a no-op.
Examples
Example 1:
- Input:
s = "ab#c",t = "ad#c" - Output:
true - Explanation: Both strings reduce to
"ac".
Example 2:
- Input:
s = "ab##",t = "c#d#" - Output:
true - Explanation: Both strings reduce to the empty string.
Example 3:
- Input:
s = "a#c",t = "b" - Output:
false - Explanation:
sreduces to"c"andtis"b", so they differ.
Example 4:
- Input:
s = "y#fo##f",t = "y#f#o##f" - Output:
true - Explanation: Both reduce to
"f".
Constraints
1 <= s.length, t.length <= 200sandtonly contain lowercase English letters and'#'characters.
Follow-up
Can you solve the problem in O(n + m) time and O(1) extra space? The stack version is O(n + m) time but O(n + m) space, and the interviewer at the screen explicitly asked for the constant-space variant.
Solution
Hints
Approach
There are two natural ways to attack this. The stack approach builds the post-edit string for each input by pushing letters and popping on '#', then compares the two stacks. It is O(n + m) time and O(n + m) extra space. The two-pointer scan from the right is what unlocks the O(1) space follow-up, and is the version most senior interviewers expect.
Key insight
Walking forward, you do not know how many backspaces will land on the current character. Walking backward, the next '#' always corresponds to a deletion of an earlier character. So if you keep a running skip counter and jump over deleted characters, the next "surviving" character pops out cleanly.
Algorithm
- Initialize two end-pointers
i = s.length - 1andj = t.length - 1, plus skip countersskipS = skipT = 0. - In a loop while either pointer is still in range, advance each side independently:
- If the current char is
'#', increment that side's skip counter and step back. - Else if the skip counter is positive, decrement it and step back (this character is deleted).
- Else stop, the pointer now points at a surviving character.
- Compare: if both pointers fell off the left end, return
true. If only one fell off, returnfalse. Otherwise compare the two surviving characters; if they differ, returnfalse. Then step both pointers back one and repeat.
Complexity
Approach Time Space
------------------ --------- --------
Stack rebuild O(n + m) O(n + m)
Two pointers (end) O(n + m) O(1)Here n = s.length and m = t.length. Both strings are scanned at most once.
Why it works
A '#' in position k deletes whatever character would have been emitted just before it. Scanning from the right, the next non-# character we care about is the first one whose pending-backspace debt is cleared. The skip counter is exactly that debt. Because the post-edit string is the same as walking the original string with a stack, comparing surviving characters in reverse order is equivalent to comparing the two post-edit strings character-by-character.
Pitfalls
- Forgetting that a
'#'on an empty buffer is a no-op. Both approaches handle it naturally (the stack stays empty, the skip counter just rises and never gets used). - Mismatched termination: if you exit the outer loop early (e.g.
while (i >= 0 && j >= 0)), the case where one string still has a pending'#'at its left edge is wrong. Usewhile (i >= 0 || j >= 0)and let the inner loops drain. - Comparing characters before fully advancing both pointers past their pending backspaces.
Solution Code