Two strings equal after their backspaces
Easy · Target 12 minutes · Two pointers· Type asked at
Bloomberg
J.P. Morgan
Citadel
You're given two strings s and t made of lower-case letters and
#. Each one is what somebody typed, and a # is a backspace that deletes the letter
before it, if there is one. Return true if the two strings end up as the same text. Can you do it in
O(1) extra space?
Examples
| Input | Output | Why |
|---|---|---|
s = "ab#c", t = "ad#c" | true | The b and the d both get deleted so each of them types ac. |
s = "ab##", t = "c#d#" | true | Every letter in both of them gets deleted and they end up as two empty strings. |
s = "a#c", t = "b" | false | The first one types c and the second types b, so they come out different. |
s = "#a#c", t = "a##c" | true | A backspace with nothing in front of it does nothing and both of them type ac. |
Constraints
- 1 ≤ s.length, t.length ≤ 200
- s and t hold lower-case letters and '#' only
Hints
Hint 1
With a stack for each string it's easy enough and it costs you O(n) space, so what is it that stops you doing it in place from the front?
Hint 2
From the front you don't know whether a letter's going to survive until you've seen what comes after it, but from the back you've already seen every # that could delete it.
Hint 3
Walk a pointer back through each string with a count of the backspaces you still owe, skip letters while that count's above zero and then compare the two letters you land on.
Where people lose marks
- Reading from the front with a pointer on each string, where you can't tell yet whether a letter's going to survive and you'll end up comparing letters that get deleted later on.
- Stopping as soon as one string runs out, when you've still got to check that the other one doesn't have any letters left that survive.
- Letting a # at the very start of a string do something, when there's nothing in front of it to delete and the count it adds just never gets used.
Dry run on "ab#c","ad#c"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5sa0b1#2c3ita0d1#2c3ji3j3
Both pointers start at the end, where every backspace that could delete a letter has already been seen.
-
Step 2 / 5sa0b1#2c3ita0d1#2c3ji3j3
Both letters that survive are c. Move both pointers left.
-
Step 3 / 5sa0ib1#2c3ta0jd1#2c3i0j0
Skip the backspaces and the letters they delete.
-
Step 4 / 5sa0ib1#2c3ta0jd1#2c3i0j0
Both letters that survive are a. Move both pointers left.
-
Step 5 / 5sa0b1#2c3ta0d1#2c3resulttrue
Both strings ran out together: they type the same text.
How to think about it
The easy way to do it is to type each string into a stack and compare the two stacks at the end,
which is O(n) time and O(n) space. If you want to get the space down you've got to read from the back, because
a # only ever deletes something to its left and so by the time you're reading a letter from the right
you've already seen every backspace that could possibly delete it.
So I keep a pointer at the end of each string and a count of backspaces I owe. To find the next letter that
survives I step left. A # adds one to the count, a letter while the count's above zero uses one up and
gets skipped, and the first letter I meet with the count at zero is the one that's really there. I do that for
both strings and compare the two letters. If they're different, or one string has run out and the other
hasn't, the answer's false. If both run out together it's true.
Complexity. Time O(n + m) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def backspace_compare(s, t):
def back(x, k): # index of the next letter that survives, or -1
skip = 0
while k >= 0:
if x[k] == '#':
skip += 1
elif skip > 0:
skip -= 1
else:
return k
k -= 1
return -1
i, j = len(s) - 1, len(t) - 1
while True:
i, j = back(s, i), back(t, j)
if i < 0 or j < 0:
return i < 0 and j < 0 # equal only if both ran out
if s[i] != t[j]:
return False
i -= 1
j -= 1#include <string>
static int back(const std::string& x, int k) { // index of the next letter that survives, or -1
int skip = 0;
for (; k >= 0; --k) {
if (x[k] == '#') ++skip;
else if (skip > 0) --skip;
else return k;
}
return -1;
}
bool solve(const std::string& s, const std::string& t) {
int i = (int)s.size() - 1, j = (int)t.size() - 1;
for (;;) {
i = back(s, i); j = back(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // equal only if both ran out
if (s[i] != t[j]) return false;
--i; --j;
}
}class Solution {
private int back(String x, int k) { // index of the next letter that survives, or -1
int skip = 0;
for (; k >= 0; k--) {
if (x.charAt(k) == '#') skip++;
else if (skip > 0) skip--;
else return k;
}
return -1;
}
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (true) {
i = back(s, i); j = back(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // equal only if both ran out
if (s.charAt(i) != t.charAt(j)) return false;
i--; j--;
}
}
}function backspaceCompare(s, t) {
const back = (x, k) => { // index of the next letter that survives, or -1
let skip = 0;
for (; k >= 0; k--) {
if (x[k] === '#') skip++;
else if (skip > 0) skip--;
else return k;
}
return -1;
};
let i = s.length - 1, j = t.length - 1;
for (;;) {
i = back(s, i); j = back(t, j);
if (i < 0 || j < 0) return i < 0 && j < 0; // equal only if both ran out
if (s[i] !== t[j]) return false;
i--; j--;
}
}// Index of the next letter that survives at or before k, or -1.
fn back(x: &[u8], mut k: i64) -> i64 {
let mut skip = 0;
while k >= 0 {
if x[k as usize] == b'#' { skip += 1; }
else if skip > 0 { skip -= 1; }
else { return k; }
k -= 1;
}
-1
}
fn solve(s: &str, t: &str) -> bool {
let (a, b) = (s.as_bytes(), t.as_bytes());
let (mut i, mut j) = (a.len() as i64 - 1, b.len() as i64 - 1);
loop {
i = back(a, i); j = back(b, j);
if i < 0 || j < 0 { return i < 0 && j < 0; } // equal only if both ran out
if a[i as usize] != b[j as usize] { return false; }
i -= 1; j -= 1;
}
}-- Read each string from the back: reverse it, then drop letters while backspaces are owed.
solve :: String -> String -> Bool
solve s t = go (reverse s) (reverse t)
where
-- the letters that survive, from the back
next skip ('#' : xs) = next (skip + 1) xs
next skip (_ : xs) | skip > 0 = next (skip - 1) xs
next _ xs = xs
go xs ys = case (next 0 xs, next 0 ys) of
([], []) -> True
(a : xs', b : ys') | a == b -> go xs' ys'
_ -> FalseVariants to try
- If the strings stream in from the front and can't be stored, you can't do it in O(1) space at all, because a later # can reach back as far as it likes.
- If there's also a key that deletes the whole word before it, the same back-to-front scan works with a flag for skipping to the previous space.
Next problems
Move the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Medium15 minKeep each value at most twice
A reader and a writer, and one comparison: a value may be written only if it differs from the value written two places back.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem →Write a solution and run it against the real test table.
Keep going
Move the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Medium15 minKeep each value at most twice
A reader and a writer, and one comparison: a value may be written only if it differs from the value written two places back.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.