Длинная подстрока без повторяющихся символов

Question

Мне задали этот вопрос в недавнем интервью. Мне нужно найти самый длинный substring без повторяющихся символов.

Дано " abcabcbb ", ответ " abc ", длина которого составляет 3.

Дано " bbbbb ", ответ " b ", длиной 1.

Дано " pwwkew ", ответ " wke ", длиной 3

Это то, что я придумал, я думаю, что это работает правильно, но интервьюер не был впечатлен и сказал, что мое решение может работать не во всех случаях.

    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

Может кто-нибудь сказать мне, в чем проблема с моим решением? Я думаю, что это один из лучших:), а также решает в O(n) время.

Answer 1

Я предполагаю, что проблема с вашим кодом заключается в том, что он становится бесполезным, когда в предложении нет повторяющихся букв во всем предложении. Как уже упоминалось в одном из комментариев, "abc" не даст правильного результата. Мой подход будет немного отличаться от вашего в следующем;

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);

В этом сокращенном коде мы изначально начинаем с такого объекта, как {last:[], test:[]} и пройтись по персонажам один за другим. Если полученный персонаж находится в наших объектах test массив мы сразу сбросим test массив, чтобы включить только букву, которую мы протестировали (p.test = [c] линия). Однако, если полученный персонаж не находится в нашем test массив затем мы делаем одну из двух вещей следующим образом. Если наш test длина массива равна или больше, чем last длина массива, то мы добавляем текущий символ test массив и сделать last массив = test массив. (p.test.length >= p.last.length ? p.test = p.last = p.test.concat(c) линия). Но если наш test длина массива короче, чем last длина массива мы просто добавляем текущий символ test Массив и продолжить аналогично до конца строки один за другим по одиночным символам.