LeetCode 3. Longest Substring Without Repeating Characters

问题描述

给定一个字符串，找出最长不重复子串的长度。

栗 1：

输入："abcabcbb"
输出：3
解释：
abc 是最长的不重复子串。

栗 2：

输入："bbbbb"
输出：1
解释：
子串为 b。

栗 3：

输入："pwwkew"
输出：3
解释：
子串为 wke。

想看英文原文的戳这里。

解题思路

我的解法

主要思想

当第一眼看到这个题目时，条件反射的想起了动态规划，因为有“最长”二字。虽然答案并不是这种思路😆。

首先，考虑这道题时需要注意两个前提条件：

子串，即连续的字符。
子串中不能有重复的字符。

而以任意一个字符开始的子串都有可能是最长不重复的。如果我们可以记录以某个字符开始，且不重复子串的最大长度，那么便可求出结果。

当遍历字符时，虽然子串长度是不断增加的，但需要判断子串是否满足上述条件，来更新记录的长度值。

主要思想是，以数组 lenList 记录从某个字符开始的最长不重复子串的长度，即数组中第 i 个元素的值，对应着以 s[i] 开头的最长不重复子串长度，s 是给定的字符串。

当遍历到某字符（下标为 i）时，需要判断该字符能否新加到原子串中。而在它前面的字符（[0, i-1]）都有可能是子串的开始字符，所以需要逐个遍历更新长度。若可以，则更新长度值，即 lenList[j] = lenList[j+1] + 1。

那么在什么情况下更新长度呢？比如遍历到第 i 个元素，要更新第 j 个元素的长度值，j < i。

条件也很简单，如下：

当第 j 个元素与它后面的字符串（也就是 [j+1, i] 区间的字符串）不重复时，则可更新。
若有重复，那么则停止更新。因为不满足条件，而前一个字符的结果依赖于后一个字符，因此 [0, j] 范围内的字符都不需要更新了。

栗子详解

举个栗子，假设字符串为 pwwekew。

当遍历到某个字符时，很显然，以该字符开始，到该字符为止的子串长度都为 1。

处理过程如下：

遍历字符 p，此时 lenList = [1]。
遍历字符 w，前面有 p 一个字符，而 pw 是满足条件的子串，此时 lenList = [2, 1]。
遍历字符 w，前面有 pw 两个字符，从后往前逐个遍历更新长度值。
- 对于 w，重复，停止更新，此时 lenList = [2, 1, 1]。
遍历字符 e，前面有 pww 三个字符，从后往前逐个遍历更新长度值。
- 对于 w，子串变为 we，lenList = [2, 1, 2, 1]。
- 对于 w，由于它后面的字符串 we 包含了 w，停止更新。最终， lenList = [2, 1, 2, 1]。
遍历字符 k，前面有 pwwe 四个字符，逐个更新长度值。
- 对于 e，子串可为 ek，lenList= [2, 1, 2, 2, 1]。
- 对于 w，子串可为 wek，lenList = [2, 1, 3, 2, 1]。
- 对于 w，有重复，停止更新。
遍历字符 e，前面有 pwwek 五个字符，逐个更新长度值。
- 对于 k，子串可为 ke， lenList = [2, 1, 3, 2, 2, 1]。
- 对于 e，ke 包含 e，停止更新。
遍历字符 w，前面有 pwweke 六个字符，逐个更新长度值。
- 对于 e，子串可为 ew，lenList = [2, 1, 3, 2, 2, 2, 1]。
- 对于 k，子串可为 kew， lenList = [2, 1, 3, 2, 3, 2, 1]。
- 对于 e，kew 包含 e，停止更新。

所以最终的结果为，lenList = [2, 1, 3, 2, 2, 2, 1]，最长连续不重复子串的长度为 3。

js 代码如下：

var lengthOfLongestSubstring = function (s) {
  // 存到以某个位置字符开始的最大长度
  let lenList = []

  // 最大长度
  let longestLen = 0
  let i = 0
  while (i < s.length) {
    // 当前元素开始的长度肯定为 1
    lenList.push(1)

    if (longestLen < 1) {
      longestLen = 1
    }

    // 遍历list，更新最大值
    let j = i - 1

    while (j >= 0) {
      // [j+1,i] 的子串
      const substr = s.substr(j + 1, i - j)

      // 是否包含字符
      if (!substr.includes(s[j])) {
        lenList[j] = lenList[j + 1] + 1

        // 记录最大值
        if (longestLen < lenList[j]) {
          longestLen = lenList[j]
        }
      } else {
        // 停止更新
        break
      }

      j -= 1
    }

    i += 1
  }

  return longestLen
};

更优解法

这种解法很巧妙，使用了滑动窗口的概念。在遍历过程中，不断更新左右边界值。

主要思想如下：

利用 map 记录字符的边界下标。
当遍历到某字符时，若在 map 中已存在，则更新窗口的左边界为该字符的边界下标，从而可计算出包含不同字符的区间长度。

比如 abca。map 中记录 a 的边界下标为 1，那么在遍历到最后一个 a 时，区间长度为 3 - 1 + 1 = 3。

注意：左边界更新时的取值应该是当前值与 map 中的值较大的那个。

比如 abba。当遍历到最后一个 a 时，左边界为 2，而此时 map 中记录的值为 1。若直接取 map 中的值，则会计算错误。

js 代码如下：

var lengthOfLongestSubstring2 = function (s) {
  // key 为字符，value 为字符的 index + 1，如果有相同的字符，可根据 value 计算出不重复的区间
  let map = new Map()
  let longestLen = 0

  let i = 0
  let j = 0
  while (i < s.length) {
    if (map.has(s[i])) {
      // 取出对应的左边界，取其最大值。因为有可能重复的字符在左边，比如 abba，遍历到最后一个 a，它对应的值是 1，而此时 j = 2， 因此需要取最大值。
      j = Math.max(map.get(s[i]), j)
    }

    const len = i - j + 1
    longestLen = Math.max(len, longestLen)

    // 设置左边界
    map.set(s[i], i + 1)
    i += 1
  }

  return longestLen
}