CareerCup

The above implementation is without O(1) space.

Below implementation is with O(1) space

function match(str, pattern){
  let CAPSLOCK = false; 
  
  let matchRec = (str, left, right) => {
    if(left > right){
      return str;
    }else{
      let char = str[left];
      if(char === "\\" && str[left+1] === 'b'){ //Backslash case
        str = str.substring(0, left - 1) + str.substring(left+2); 
        left--;
      }else if(char === "\\" && str[left+1] === 'c'){
        CAPSLOCK = !CAPSLOCK;
        str = str.substring(0, left) + str.substring(left+2); 
      }else{
        if(CAPSLOCK){
          str = str.substring(0, left) + str.charAt(left).toUpperCase() + str.substring(left+1);    
        }
        left++;
      }
      return matchRec(str, left, str.length - 1);
    }
  };
  console.log("str '" +str + "' and pattern '" + pattern +"' matches ==> " );
  str = matchRec(str, 0, str.length - 1);
  return str === pattern;
}

console.log(match("abc\\b", "ab"));
console.log(match("abc\\ca", "abcA"));
console.log(match("abc\\bde\\cfd", "abdeFD"));
console.log(match("\\ba", "a"));
console.log(match("abc\\cde\\cfd", "abcDEfd"));
console.log(match("a\\ba", "a"));
console.log(match("a\\b\\cb", "B"));
console.log(match("a\\b", ""));
console.log(match("\\cz", "Z"));
console.log(match("Abc\\b\\bt", "At"));
console.log(match("\\caef\\b\\c\\bt", "At"));
console.log(match("\\ca", "A"));

Javascript Implementation -

function match(str, pattern){
  let BACKSLASH = false;
  let CAPSLOCK = false; 
  let stack = [];
  
  str.split('').forEach((char, index) => {
    if(char === "\\"){
      BACKSLASH = !BACKSLASH; 
    }else{
      if(BACKSLASH && char === 'b'){
        stack.pop();
        BACKSLASH = !BACKSLASH;
      }
      else if(BACKSLASH && char === 'c'){
        CAPSLOCK = !CAPSLOCK;
        BACKSLASH = !BACKSLASH;
      }
      else{
        stack.push(CAPSLOCK ? char.toUpperCase() : char);
      }  
    }
  });
  return stack.join('') === pattern;
}



console.log(match("abc\\b", "ab"));
console.log(match("abc\\ca", "abcA"));
console.log(match("abc\\bde\\cfd", "abdeFD"));
console.log(match("\\ba", "a"));
console.log(match("abc\\cde\\cfd", "abcDEfd"));
console.log(match("a\\ba", "a"));
console.log(match("a\\b\\cb", "B"));
console.log(match("a\\b", ""));
console.log(match("\\cz", "Z"));
console.log(match("Abc\\b\\bt", "At"));
console.log(match("\\caef\\b\\c\\bt", "At"));

I present my solution to this problem below. I assume that backslash+b represents backspace and backslash+c represents the caps lock. The hardest part about this problem is a shit ton of edge cases. I use python's pop() function to modify the list in place since the problem states to solve it in O(1) SC.

Other than that, the main idea is to keep track of two pointers, current and next. If it is backspace, carefully remove the escape characters and the previous character to be deleted. If it is caps lock, carefully remove the escape characters and modify the next+1 pointer to be uppercase.

Solution:

def isValid(inputString):
  # There can't be a single backslash character as the string
  if len(inputString) == 1 and inputString[0] == '\\':
    return False
  # Backspace can't occur at beginning of a string
  if len(inputString) >= 2 and inputString[0] == '\\' and inputString[1] == 'b':
    return False
  # You can't have just a caps lock character in your string
  if len(inputString) == 2 and inputString[0] == '\\' and inputString[1] == 'c':
    return False
  # Can't have just a caps lock string at the end
  if len(inputString) >= 2 and inputString[-2] == '\\' and inputString[-1] == 'c':
    return False

  for i in range(len(inputString)-3):
    temp = inputString[i:i+4]
    # Caps lock can't be immediately followed by backspace
    if temp[0:2] == r'\c' and temp[2:4] == r'\b':
      return False

  return True


def compareStrings(specialString, secondString):
  specialString = list(specialString)
  if not isValid(specialString):
    print('*** Invalid input string. Characters are not properly escaped! ***')
    return False

  curr = 0
  next = 1
  while curr < len(specialString) - 1:
    if specialString[curr] == '\\' and specialString[next] == 'c':
      specialString[next+1] = specialString[next+1].upper()
      specialString.pop(next)
      specialString.pop(curr)

    if specialString[curr] == '\\' and specialString[next] == 'b':
      specialString.pop(next)
      specialString.pop(curr)
      curr = curr - 1
      specialString.pop(curr)
    else:
      curr = curr + 1
    next = curr + 1
  return ''.join(specialString) == secondString

print(compareStrings('abc\\b', 'ab')) # True
print(compareStrings('abc\\bxy\cz', 'abxyZ')) # True
print(compareStrings('a\\ba', 'a')) # True
print(compareStrings('a\\b\cb', 'B')) # True
print(compareStrings('abc\ca', 'abcA')) # True
print(compareStrings('a\\b', '')) # True
print(compareStrings('\cz', 'Z')) # True

If it's ok to destroy the input, we can do one pass backward, counting backspaces and replacing the chars which will be removed by 0, another pass forward, tracking state of the CapsLock and replacing chars with upper case when needed, and the final pass, comparing non-zeroed non-slashed chars.

If it's not ok to destroy the input, my idea is to find the next characters which will not be removed and compare them. Space is O(1), but time is O(N^2):

#include <iostream>
#include <string>

using namespace std;

int GetNext(string const &s, int idx, bool &caps)
{
    for (int i = idx + 1; i < s.size(); ++i) {
        if (s[i] == '\\') {
            if (s[i + 1] == 'c') {
                caps = !caps;
            }
            ++i;
        } else {
            int chars_count = 0;
            int bs_count = 0;
            bool char_will_be_removed = false;
            for (int j = i; j < s.size() && !char_will_be_removed; ++j) {
                if (s[j] == '\\') {
                    if (s[j + 1] == 'b') {
                        if (++bs_count >= chars_count) {
                            char_will_be_removed = true;
                        }
                    }
                    ++j;
                } else {
                    ++chars_count;
                }
            }
            if (!char_will_be_removed) {
                return i;
            }
        }
    }
    return -1;
}

bool Compare(string const &s1, string const &s2)
{
    bool caps1 = false;
    bool caps2 = false;
    int i = -1;
    int j = -1;
    while (true) {
        i = GetNext(s1, i, caps1);
        j = GetNext(s2, j, caps2);
        if ((i == -1) && (j == -1)) {
            return true;
        }
        if ((i == -1) || (j == -1)) {
            return false;
        }
        char c1 = caps1 ? toupper(s1[i]) : s1[i];
        char c2 = caps2 ? toupper(s2[j]) : s2[j];
        if (c1 != c2) {
            return false;
        }
    }
}

int main()
{
    cout << Compare("Abc\\b\\bt", "\\caef\\b\\c\\bt") << "\n";
}

def compare_strings_with_escape_characters(s1: str, s2: str) -> bool:
bs, cl = ['\\', 'b'], ['\\', 'c']
s1, s2 = list(s1), list(s2)
if s1[:2] == bs: s1 = s1[2:]
if s1[-2:] == cl: s1 = s1[:-2]
for i in range(len(s1) - 3):
if s1[i:i+2] == cl:
s1.pop(i)
s1.pop(i)
s1[i] = s1[i].upper()
if s1[i+1:i+3] == bs:
s1.pop(i)
s1.pop(i)
s1.pop(i)
return s1 == s2


if __name__ == '__main__':
assert compare_strings_with_escape_characters(r'fooo\bBA\cr', 'fooBAR')
assert compare_strings_with_escape_characters(r'\bfoo', 'foo')
assert compare_strings_with_escape_characters(r'foo\c', 'foo')

def compare_strings_with_escape_characters(s1: str, s2: str) -> bool:
    bs, cl = ['\\', 'b'], ['\\', 'c']
    s1, s2 = list(s1), list(s2)
    if s1[:2] == bs: s1 = s1[2:]
    if s1[-2:] == cl: s1 = s1[:-2]
    for i in range(len(s1) - 3):
        if s1[i:i+2] == cl:
            s1.pop(i)
            s1.pop(i)
            s1[i] = s1[i].upper()
        if s1[i+1:i+3] == bs:
            s1.pop(i)
            s1.pop(i)
            s1.pop(i)
    return s1 == s2


if __name__ == '__main__':
    assert compare_strings_with_escape_characters(r'fooo\bBA\cr', 'fooBAR')
    assert compare_strings_with_escape_characters(r'\bfoo', 'foo')
    assert compare_strings_with_escape_characters(r'foo\c', 'foo')

private static boolean isStringsSimilar(String longStr, String shortStr)
{
int longStrIndex = longStr.length()-1;
int shortStrIndex = shortStr.length()-1;


while(longStrIndex >=0 && shortStrIndex >=0)
{
if(longStrIndex > 0 && longStr.charAt(longStrIndex) == 'b'
&& longStr.charAt(longStrIndex - 1) == new Character('\\'))
{
longStrIndex = longStrIndex -3;
continue;
}
else if(longStrIndex > 1 && longStr.charAt(longStrIndex -1) == 'c'
&& longStr.charAt(longStrIndex -2) == new Character('\\'))
{
if(Character.toUpperCase(longStr.charAt(longStrIndex)) != shortStr.charAt(shortStrIndex))
{
return false;
}

longStrIndex = longStrIndex -3;
}
else
{
if(longStr.charAt(longStrIndex) != shortStr.charAt(shortStrIndex))
{
return false;
}
longStrIndex--;
}
shortStrIndex--;
}

return (longStrIndex < 0 && shortStrIndex < 0);
}