Backspace String. Solving Google interview question.
Tags: javascript, career, beginners, tutorial
Published: 2020-04-29 14:49:16

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.

<h2>Brute Force / Stack Based: O(n) Time and O(n) Space </h2> 

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.

```javascript
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. 

<h2>Optimization</h2>

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. 

<strong>Pattern 1 : One of the string is empty</strong>
S = "abcd" T = ""
S = ""     T = "adgre"

for this optimization we could check if any of the strings are empty.
```javascript 
let slen = S.length;
let tlen = T.length;
if(slen == 0 || tlen == 0) return slen == tlen;
```

💡 check if any of the strings are empty

<strong>Pattern 2 : Strings that don't end with # </strong>
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. 

```javascript
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.

<strong>Pattern 3 : Sub strings that effective cancel themselves ? </strong>
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.

```javascript
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.

<strong>Pattern 4: what if there are no '#' ? </strong>
S = "abcdef"  T = "mnodef"
 
When there is no '#', we could just compare two string character by character from the end.

```javascript
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:

```javascript
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