没有重复字符的最长子串极端情况

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

在这个 reduce 代码中，我们首先从 {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 数组并继续同样地一直到字符串的末尾一个接一个单个字符。

没有重复字符的最长子串极端情况

Longest Substring Without Repeating Characters corner cases

javascript

arrays

string

time-complexity

asymptotic-complexity