Question: Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Eg: if S = ab#c and T = ad#c, after operations, S = ac and T = ac. So return true.

if S = a###d and T = a#x#, after operations, S = d and T = "". So return false.

if S = a#c# and T = b#d#, after operations, S = "" and T = "", so return true.

## Brute Force / Stack Based: O(n) Time and O(n) Space

The First thing which rings the bell after seeing the above examples is using stack.

For String S.

Step 1> if the current letter is "a"-"z" push it onto the stack.

Step 2> if the current letter is "#" check is the stack is not empty and pop from the stack.

And repeat the same for T.

So let's code it.

```
var backspaceCompare = function(S, T) {
let sarr = [];
let tarr = [];
for(let s of S){
if(s == '#'){
if(sarr.length>0){
sarr.pop();
}
}else{
sarr.push(s);
}
}
for(let t of T){
if( t == '#'){
if(tarr.length>0){
tarr.pop();
}
}else{
tarr.push(t);
}
}
if(tarr.length != sarr.length) return false;
return tarr.join('') == sarr.join('');
};
```

At Google, they expected the candidate to solve it with O(n) time and O(1) space.

## Optimization

One way of optimizing and look for patterns is to try out different combinations of input and most importantly looking for edge cases and observations.

**Pattern 1 : One of the string is empty**

S = "abcd" T = ""

S = "" T = "adgre"

for this optimization we could check if any of the strings are empty.

```
let slen = S.length;
let tlen = T.length;
if(slen == 0 || tlen == 0) return slen == tlen;
```

ðŸ’¡ check if any of the strings are empty

**Pattern 2 : Strings that don't end with # **

S = "ab##c#d" T = "ae##f#b"

if both the strings aren't ending with #, we don't care what lies behind them since if the last characters aren't the same, the rest won't matter.

```
if(S[s.length-1] != '#' && T[t.length-1] != '#')
return S[s.length-1] == T[t.length-1];
```

ðŸ’¡ Iterate from the end of strings to compare the last characters which we actually care about.

**Pattern 3 : Sub strings that effective cancel themselves ? **

S = "abcde####" T = "mnop####"

Since we will be iterating on both the string from the end, if the last character is not '#' and not equal then return false.

But if the last character is '#' then we count the number of '#' from that point where we come across the first non-'#' character or reach the start of the string.

Then we move that many counts back towards the start of the string to simulate deleting a character.

And from that point it's similar to comparing the end of the strings.

```
let countS = 0;
let countT = 0;
let i = S.length-1;
let j = S.length-1;
while(i!=0 && j!=0){
//cancle out from first string
while(i>0 && (countS>0 || S[i] == '#')) S[i--] == '#' ? countS++:countS--;
//cancle out the second string
while(j>0 && (countT>0 || T[j] == '#')) T[j--] == '#' ? countT++:countT--;
// compare the last characters left after canclelling.
if(S[i--] != T[j--]) return false;
}
```

ðŸ’¡ Count the number of '#', move back towards the start equal counts, and compare the strings.

**Pattern 4: what if there are no '#' ? **

S = "abcdef" T = "mnodef"

When there is no '#', we could just compare two string character by character from the end.

```
while(i>=0 && j>=0){
if(S[i--] != T[j--]) return false;
}
return true;
```

ðŸ’¡ For a case when there might be no '#', just keep on comparing the end of strings.

So putting them all together:

```
var backspaceCompare = function(S, T) {
let i = S.length-1;
let j = T.length-1;
let countS = 0;
let countT = 0;
while(i>=0 || j>=0){
while(i>=0 && (S[i] == '#' || countS>0)) S[i--] == '#' ? ++countS: --countS;
while(j>=0 && (T[j] == '#' || countT>0)) T[j--] == '#' ? ++countT: --countT;
//since index is zero based,
//i=-1 and j=-1 is only way to confirm that pointers had reached start of the strings.
if(i < 0 || j < 0) return i == j;
if(S[i--] != T[j--]) return false;
}
return i == j;
};
```

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/backspaceString.js

## Top comments (0)