Community Problem
Backspace String Compare
Difficulty: Easy
Compare two strings after applying backspace edits, with the catch that the O(1) space version uses two pointers walking from the end.
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