Backspace String. Solving Google interview question.

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