Backspace String Compare
Backspace String Compare is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers from the end), runs in O(n + m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (build both strings with a stack) up.
Problem
You are given two strings s and t. Each one describes keys pressed in an empty text editor: a lowercase letter types that letter, and '#' is a backspace that deletes the last typed letter (if the text is empty, it does nothing).
Return true if typing s and typing t produce the same final text, and false otherwise.
Examples
Example 1
- Input
s = "xy#z", t = "xw#z"- Output
true- Why
- Both strings end up as "xz" after the backspaces are applied.
Example 2
- Input
s = "m##n", t = "#n"- Output
true- Why
- The second # in s hits an empty editor and does nothing, so both become "n".
Example 3
- Input
s = "a#b", t = "b#a"- Output
false- Why
- s becomes "b" while t becomes "a".
Constraints
1 <= s.length, t.length <= 200sandtcontain only lowercase letters and'#'.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (build both strings with a stack) | O(n + m) | O(n + m) |
| Optimal (two pointers from the end) | O(n + m) | O(1) |
1Brute force (build both strings with a stack)
O(n + m)Each character is processed once.O(n + m)The built strings can be as long as the inputs.Type each string into a stack: push letters and pop on # when the stack is not empty. Then compare the two results.
- build(str): for each character, if it is '#' pop when non-empty, otherwise push.
- Return build(s).equals(build(t)).
class Solution {
public boolean backspaceCompare(String s, String t) {
return build(s).equals(build(t));
}
private String build(String str) {
StringBuilder sb = new StringBuilder();
for (char c : str.toCharArray()) {
if (c == '#') {
if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
}
}
return sb.toString();
}
}class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
return self.build(s) == self.build(t)
def build(self, text: str) -> str:
stack = []
for ch in text:
if ch == '#':
if stack:
stack.pop()
else:
stack.append(ch)
return "".join(stack)class Solution {
string build(const string& str) {
string out;
for (char c : str) {
if (c == '#') {
if (!out.empty()) out.pop_back();
} else {
out.push_back(c);
}
}
return out;
}
public:
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};function backspaceCompare(s, t) {
const build = (str) => {
const stack = [];
for (const c of str) {
if (c === '#') {
if (stack.length > 0) stack.pop();
} else {
stack.push(c);
}
}
return stack.join("");
};
return build(s) === build(t);
}2Optimal (two pointers from the end)
O(n + m)Each index of both strings is visited once.O(1)Only the pointers and two skip counters.Walk both strings from right to left. Keep a count of pending backspaces for each: a # increases it, and a letter met while the count is positive is skipped (decreasing the count). When both pointers rest on a surviving letter, those letters must match. The strings are equal when both run out at the same time.
- i = s.length - 1, j = t.length - 1.
- Loop: move i left to the next surviving letter of s (or -1), the same for j in t.
- If both are -1, return true. If only one is -1 or s[i] != t[j], return false.
- Decrease i and j and continue.
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (true) {
i = nextLetter(s, i);
j = nextLetter(t, j);
if (i < 0 && j < 0) return true;
if (i < 0 || j < 0 || s.charAt(i) != t.charAt(j)) return false;
i--;
j--;
}
}
private int nextLetter(String str, int idx) {
int skip = 0;
while (idx >= 0) {
if (str.charAt(idx) == '#') {
skip++;
} else if (skip > 0) {
skip--;
} else {
break;
}
idx--;
}
return idx;
}
}class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while True:
i = self.next_letter(s, i)
j = self.next_letter(t, j)
if i < 0 and j < 0:
return True
if i < 0 or j < 0 or s[i] != t[j]:
return False
i -= 1
j -= 1
def next_letter(self, text: str, idx: int) -> int:
skip = 0
while idx >= 0:
if text[idx] == '#':
skip += 1
elif skip > 0:
skip -= 1
else:
break
idx -= 1
return idxclass Solution {
int nextLetter(const string& str, int idx) {
int skip = 0;
while (idx >= 0) {
if (str[idx] == '#') {
skip++;
} else if (skip > 0) {
skip--;
} else {
break;
}
idx--;
}
return idx;
}
public:
bool backspaceCompare(string s, string t) {
int i = s.size() - 1, j = t.size() - 1;
while (true) {
i = nextLetter(s, i);
j = nextLetter(t, j);
if (i < 0 && j < 0) return true;
if (i < 0 || j < 0 || s[i] != t[j]) return false;
i--;
j--;
}
}
};function backspaceCompare(s, t) {
const nextLetter = (str, idx) => {
let skip = 0;
while (idx >= 0) {
if (str[idx] === '#') {
skip++;
} else if (skip > 0) {
skip--;
} else {
break;
}
idx--;
}
return idx;
};
let i = s.length - 1, j = t.length - 1;
while (true) {
i = nextLetter(s, i);
j = nextLetter(t, j);
if (i < 0 && j < 0) return true;
if (i < 0 || j < 0 || s[i] !== t[j]) return false;
i--;
j--;
}
}Edge cases to test
- A backspace on empty text does nothing
- Both strings become empty (for example
"a#"and"##") - Several backspaces in a row that delete several letters
- Strings of different lengths that still produce the same text
Hints
Hint 1
Simulate the typing: a letter is added, # removes the most recent letter if there is one. A stack does exactly that.
Hint 2
Can you avoid building the strings? Read from the back: a # tells you to skip the next letter you meet going left.
Hint 3
Use one pointer per string, starting at the end. Move each to its next surviving letter, compare, and step both.
FAQ
What is the best time complexity for Backspace String Compare?
Optimal (two pointers from the end) runs in O(n + m) time and O(1) extra space. Each index of both strings is visited once.
Which pattern does Backspace String Compare use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Backspace String Compare?
Yes. Brute force (build both strings with a stack) takes O(n + m) time and O(n + m) space. Type each string into a stack: push letters and pop on when the stack is not empty.
Which edge cases should I test for Backspace String Compare?
A backspace on empty text does nothing; Both strings become empty (for example "a" and ""); Several backspaces in a row that delete several letters; Strings of different lengths that still produce the same text.