Backspace String Compare — Solution in Python, Java & C++
Backspace String Compare solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Backspace String Compare is an easy coding problem on strings, two pointers and stack.
- Difficulty: Easy
- Topics: Strings, Two Pointers, Stack
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings s and t, return true if they are equal when both are typed into empty text editors, where # means backspace.
Backspacing an empty editor leaves it empty.
Example 1
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both become "ac".
Example 2
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both become "".
Example 3
Input: s = "a#c", t = "b"
Output: false
Constraints
1 <= s.length, t.length <= 20Lowercase letters and '#'.
Hints for Backspace String Compare
Hint 1
A stack simulates typing directly.
Hint 2
The O(1)-space version walks both strings backwards, counting pending backspaces.
How to solve Backspace String Compare
Scanning forwards is awkward because a backspace refers to something already typed. Scanning backwards fixes that: when you meet a # you know it will consume the next real character to the left, so carry a counter of pending deletions and skip that many characters. Walk both strings backwards in step and compare the surviving characters.
Approach
- Put
iat the end ofsandjat the end oft. - Advance
ileftwards to the next surviving character: a#increments a skip counter, and a normal character is discarded (decrementing the counter) while the counter is positive. - Do the same for
jint. - If both landed on a character, they must match; if only one did, the strings differ in length after editing — return
false. - Step both pointers past the compared characters and repeat until both are exhausted.
Why it works
Reading right to left makes each # refer to characters not yet visited, so the effect of every backspace is known before its victim is reached — no lookahead or rewriting is needed. The surviving characters emerge in reverse order of the final text, so comparing them pairwise is exactly comparing the two edited strings. Building both strings with a stack is equally correct and easier to write, at the cost of O(n) extra space.
Complexity
- Time —
O(|s| + |t|) - Space —
O(1)
Pitfalls
- The loop must continue while either pointer still has characters — stopping when one runs out misses a length mismatch.
- Backspacing an empty editor is a no-op, which the counter handles by simply never going negative.
- Consecutive
#s stack up; the skip counter must accumulate rather than being a boolean. - After comparing a pair, move both pointers on — leaving one in place re-compares the same character.
Reference solution
Python
def backspaceCompare(s: str, t: str) -> bool:
def build(x: str) -> str:
st = []
for ch in x:
if ch == "#":
if st:
st.pop()
else:
st.append(ch)
return "".join(st)
return build(s) == build(t)Java
public static boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
int skip = 0;
while (i >= 0) {
if (s.charAt(i) == '#') {
skip++;
i--;
} else if (skip > 0) {
skip--;
i--;
} else break;
}
skip = 0;
while (j >= 0) {
if (t.charAt(j) == '#') {
skip++;
j--;
} else if (skip > 0) {
skip--;
j--;
} else break;
}
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) return false;
} else if (i >= 0 || j >= 0) {
return false;
}
i--;
j--;
}
return true;
}C++
bool backspaceCompare(string s, string t) {
int i = (int) s.size() - 1, j = (int) t.size() - 1;
while (i >= 0 || j >= 0) {
int skip = 0;
while (i >= 0) {
if (s[i] == '#') {
skip++;
i--;
} else if (skip > 0) {
skip--;
i--;
} else break;
}
skip = 0;
while (j >= 0) {
if (t[j] == '#') {
skip++;
j--;
} else if (skip > 0) {
skip--;
j--;
} else break;
}
if (i >= 0 && j >= 0) {
if (s[i] != t[j]) return false;
} else if (i >= 0 || j >= 0) {
return false;
}
i--;
j--;
}
return true;
}JavaScript
var backspaceCompare = function(s, t) {
function build(x) {
const st = [];
for (const ch of x) {
if (ch === "#") st.pop();
else st.push(ch);
}
return st.join("");
}
return build(s) === build(t);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique