第 3 期(2019-05-10)：无重复字符的最长子串

[binperson]

来源：leetcode
难度：★★★

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

---

本期优秀回答者： @cnyballk

[cnyballk]

const get666Length = s => {
  if (s.length < 2) return s.length;
  let index,
    i = 1,
    discardLength = 0,
    max = 0;
  for (; i < s.length; i++) {
    index = s.lastIndexOf(s[i], i - 1);
    if (index !== -1) {
      max = Math.max(max, i - discardLength);
      discardLength = Math.max(discardLength, index + 1);
    }
  }
  return Math.max(max, i - discardLength);
};

[wingmeng]

这题还是有点难度的，一开始是打算用“双指针”来解的，后来感觉用正则表达式更优雅。

const noRepeatSubstrLen = str => {
  let len = str ? str.length : 0;

  // 空字符和1个字符的情况
  if (len < 2) {
    return len;
  }

  let arr = [
    ...new Set(  // 去重
      str.split(/(.+?)(\1)/g)  // 贪婪模式匹配所有连续字符
    )
  ].map(s => s.length);  // 去重后统计每项的字符串长度
  
  return Math.max.apply(null, arr);
}

console.log(noRepeatSubstrLen(''));  // 0
console.log(noRepeatSubstrLen('a'));  // 1
console.log(noRepeatSubstrLen('ab'));  // 2
console.log(noRepeatSubstrLen('aa'));  // 1
console.log(noRepeatSubstrLen('abcabcbb'));  // 3
console.log(noRepeatSubstrLen('bbbbb'));  // 1
console.log(noRepeatSubstrLen('pwwkew'));  // 3
console.log(noRepeatSubstrLen('qqwewert'));  // 2

[liwenkang]

我的怕是会超时⊙﹏⊙

// 求无重复字符的最长子串
const getMaxCount = (string) => {
    // 计算最长不重复连续字符的个数
    const getCount = (string, lastStr = '') => {
        lastStr = lastStr ? lastStr : string[0];
        for (let i = 1; i < string.length; i++) {
            if (lastStr.includes(string[i])) {
                // 有重复的,直接输出
                return lastStr.length;
            } else {
                // 没有重复的,继续循环
                lastStr += string[i];
                getCount(string, lastStr);
            }
        }
        return lastStr.length;
    };

    let max = 0;
    for (let i = 0; i < string.length; i++) {
        let count = getCount(string.slice(i));
        if (count > max) {
            max = count;
        }
    }
    return max;
};