Backspace String Compare
Description
You get two strings, s and t, made of lowercase letters and #. Type each one into an empty text editor, where # is a backspace: it deletes the character before it. Return true if both end up as the same text.
A backspace on empty text does nothing: the text stays empty.
Follow-up: can you do it in O(n) time and O(1) extra space?
Examples
Example 1
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: In s the # deletes the b, so s types "ac". In t the # deletes the d, so t types "ac" too: true.
Example 2
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Two backspaces delete both letters of s, and each letter of t is deleted right after it's typed. Both type an empty text: true.
Example 3
Input: s = "a#c", t = "b"
Output: false
Explanation: s types "c" and t types "b": false.
Constraints
- 1 ≤ s.length, t.length ≤ 200
- s and t contain only lowercase letters and '#' characters
Editorial
Brute Force
Intuition
Do what an editor does. Read each string left to right and keep the text typed so far as a stack: a letter is pushed, a # pops the last letter if there is one. Then compare the two typed texts.
Step-by-Step Explanation
Let's trace s = "ab#c", t = "ad#c":
- s: type a, type b, # deletes b, type c. s types "ac".
- t: type a, type d, # deletes d, type c. t types "ac".
- "ac" equals "ac": true.
Type Both Strings With a Stack — Each string is typed into its own stack (bottom row); then the two typed texts are compared.
Algorithm
- For each string, make an empty stack. For each character: if it's a letter, push it; if it's
#and the stack isn't empty, pop. - Return whether the two stacks hold the same letters.
Code
class Solution {
public:
bool backspaceCompare(string s, string t) {
return typed(s) == typed(t);
}
private:
// the text a string types into an empty editor
string typed(const string& text) {
string out; // used as a stack
for (char c : text) {
if (c != '#') out.push_back(c);
else if (!out.empty()) out.pop_back(); // a backspace on empty text does nothing
}
return out;
}
};
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
return self.typed(s) == self.typed(t)
def typed(self, text: str) -> str:
"""The text a string types into an empty editor."""
stack = []
for c in text:
if c != "#":
stack.append(c)
elif stack: # a backspace on empty text does nothing
stack.pop()
return "".join(stack)
class Solution {
public boolean backspaceCompare(String s, String t) {
return typed(s).equals(typed(t));
}
// the text a string types into an empty editor
private String typed(String text) {
StringBuilder out = new StringBuilder(); // used as a stack
for (char c : text.toCharArray()) {
if (c != '#') out.append(c);
else if (out.length() > 0) out.deleteCharAt(out.length() - 1); // a backspace on empty text does nothing
}
return out.toString();
}
}
var backspaceCompare = function(s, t) {
return typed(s) === typed(t);
};
// the text a string types into an empty editor
function typed(text) {
const stack = [];
for (const c of text) {
if (c !== '#') stack.push(c);
else if (stack.length > 0) stack.pop(); // a backspace on empty text does nothing
}
return stack.join('');
}
Complexity Analysis
Time Complexity: O(n + m)
Each character is pushed or popped once, and the comparison reads each typed text once.
Space Complexity: O(n + m)
Both typed texts are stored.
Why This Approach Is Not Efficient
It's already linear in time; the follow-up asks to drop the O(n + m) extra space, so the typed texts can't be stored.
Without storing anything, could you compare the strings from the front? No: when you reach a letter, you don't know yet whether a # further on will delete it.
From the back you do. Every # is met before the letters it deletes, so a count of pending backspaces says at once whether the letter you're on survives. Walk both strings backwards, letter by surviving letter, and compare as you go.
Optimal Approach - Two Pointers
Intuition
Put one pointer at the end of each string. Each pointer moves left to its string's next surviving letter: a # adds one to a count of backspaces still to apply; a letter met while that count is above zero is deleted (and the count drops by one); a letter met at zero survives.
Compare the two survivors. If they differ, so do the texts. If one string runs out of survivors and the other doesn't, the texts differ too. If both run out together, every letter matched: true.
Step-by-Step Explanation
Let's trace s = "ab#c", t = "ad#c":
- Moving left from s[3] and t[3], the next survivors are s[3] = 'c' and t[3] = 'c'. They're the same; move both pointers left.
- Moving left from s[2] and t[2], the next survivors are s[0] = 'a' and t[0] = 'a'. They're the same; move both pointers left.
- Both strings run out of surviving letters at the same time.
On the way, each pointer met one #, which deleted the b in s and the d in t. The answer is true.
Read Both Strings From the Back — Each pointer moves left to its next surviving letter; matched survivors turn green.
Algorithm
- Set
ito the last index ofsandjto the last index oft. - Repeat:
- move
ito the next surviving letter at or before it (or -1), and the same forj; - if either is -1, return whether both are;
- if
s[i] != t[j], return false; - move both one step left.
- move
Code
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = (int)s.size() - 1, j = (int)t.size() - 1;
while (true) {
i = nextKept(s, i);
j = nextKept(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // the same text only if both run out together
if (s[i] != t[j]) return false;
i--;
j--;
}
}
private:
// the index of the next letter at or before k that survives the backspaces, or -1
int nextKept(const string& text, int k) {
int skip = 0; // backspaces seen that still have a letter to delete
while (k >= 0) {
if (text[k] == '#') skip++;
else if (skip > 0) skip--; // a later # deletes this letter
else return k;
k--;
}
return -1;
}
};
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while True:
i, j = self.next_kept(s, i), self.next_kept(t, j)
if i < 0 or j < 0:
return i < 0 and j < 0 # the same text only if both run out together
if s[i] != t[j]:
return False
i -= 1
j -= 1
def next_kept(self, text: str, k: int) -> int:
"""The index of the next letter at or before k that survives the backspaces, or -1."""
skip = 0 # backspaces seen that still have a letter to delete
while k >= 0:
if text[k] == "#":
skip += 1
elif skip > 0:
skip -= 1 # a later # deletes this letter
else:
return k
k -= 1
return -1
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (true) {
i = nextKept(s, i);
j = nextKept(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // the same text only if both run out together
if (s.charAt(i) != t.charAt(j)) return false;
i--;
j--;
}
}
// the index of the next letter at or before k that survives the backspaces, or -1
private int nextKept(String text, int k) {
int skip = 0; // backspaces seen that still have a letter to delete
while (k >= 0) {
if (text.charAt(k) == '#') skip++;
else if (skip > 0) skip--; // a later # deletes this letter
else return k;
k--;
}
return -1;
}
}
var backspaceCompare = function(s, t) {
let i = s.length - 1, j = t.length - 1;
while (true) {
i = nextKept(s, i);
j = nextKept(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // the same text only if both run out together
if (s[i] !== t[j]) return false;
i--;
j--;
}
};
// the index of the next letter at or before k that survives the backspaces, or -1
function nextKept(text, k) {
let skip = 0; // backspaces seen that still have a letter to delete
while (k >= 0) {
if (text[k] === '#') skip++;
else if (skip > 0) skip--; // a later # deletes this letter
else return k;
k--;
}
return -1;
}
Complexity Analysis
Time Complexity: O(n + m)
Each pointer only moves left, over each character once.
Space Complexity: O(1)
Two indexes and two small counts.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Popping a backspace from an empty stack. stack.pop()
On s = "#a", t = "a" it crashes with IndexError: pop from empty list; the answer is true. A backspace on empty text does nothing, but stack.pop() on an empty list crashes (Python raises IndexError, Java throws). Check that something is there before you delete it.
Skipping exactly one letter per # from the back. k -= 2
On s = "abc##", t = "a" it returns false; the answer is true. Jumping back two places at a # assumes the character before it is a letter to delete. In "abc##" it's another #, so the jump spends itself on that # and lands on the c, which survives, and so does the b, though both should be deleted. Count the pending backspaces instead.
Calling it equal when one string runs out first. if i < 0 or j < 0: return True
On s = "a", t = "ba" it returns true; the answer is false. The loop stops as soon as either string has no letters left, and then everything matched so far is taken as equal. If the other string still has a surviving letter, the texts differ: both have to run out together.
Where This Pattern Is Taught
This problem practises two pointers on two inputs, read from the back. It's taught in Two Pointers on Two Arrays or Strings, along with why reading from the back is what makes O(1) space possible.