Longest Substring Without Repeating Characters corner cases

Question

I was asked this question in a recent interview. I need to find the longest substring without repeating characters.

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3

This is what I came up with, I think it works correctly, but the interviewer was not impressed and said that my solution may not work for all cases.

    var str = "pwwkew";
    var longSubstring = function(str) {
      var obj = {}; //map object
      var count = 0;
      var c = []; //count array to keep the count so far
      for (var i = 0; i < str.length; ++i) {
        //check if the letter is already in the map
        if (str[i] in obj && obj[str[i]] !== i) {
          c.push(count); //we encountered repeat character, so save the count
          obj = {};
          obj[str[i]] = i;
          count = 1;
          continue;
        } else {
          obj[str[i]] = i;
          ++count;
        }
      }
      return Math.max.apply(null, c);
    }
    console.log(longSubstring(str)); //prints 3

Can anyone tell me what's the problem with my solution? I think it is one of the best :) and also solves in O(n) time.

Answer 1

I guess the problem with your code is, it gets haywire when there is no repeating letters in the whole sentence to start with. As mentioned in one of the comments "abc" won't produce a correct result. My approach would be slightly different than yours as follows;

var str = "pwwkew",
   data = Array.prototype.reduce.call(str, (p,c) => (p.test.includes(c) ? p.test = [c]
                                                                        : p.test.length >= p.last.length ? p.test = p.last = p.test.concat(c)
                                                                                                         : p.test.push(c)
                                                                        , p), {last:[], test:[]}),
result = data.last.length;
console.log(data);
console.log(result);

In this reduce code we initially start with an object like {last:[], test:[]} and go over the characters one by one. If the received character is in our objects's test array we immediately reset the test array to include only the letter we tested (the p.test = [c] line). However If the received character is not in our test array then we do either one of the two thing as follows. If our test array's length is equal or longer than the last array's length then we add the current character to test array and make last array = test array. (p.test.length >= p.last.length ? p.test = p.last = p.test.concat(c) line). But if our test array's length is shorter than the last array's length we just add the current character to test array and continue likewise all the way to the end of the string one by one over single characters.