#3. 无重复字符的最长子串

LeetCode 原题链接

#题目描述

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

示例：

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

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

#1. 题型判断

本题要求的是“不含重复字符的最长子串”。

子串要求字符必须连续，题目又要求在连续区间中维护“不重复”这个条件，所以可以使用滑动窗口。

窗口右边界不断向右扩展，表示尝试加入新的字符；如果加入新字符后出现重复，就移动左边界，让窗口重新变成无重复字符的合法窗口。

#2. 指针含义

使用闭区间窗口 [left, right]。

• left：当前无重复字符窗口的左边界。
• right：当前无重复字符窗口的右边界，也是正在遍历的新字符位置。
• lastIndexMap：记录每个字符最近一次出现的下标。
• ans：记录当前找到的最长无重复子串长度。

例如遍历到 right 时，窗口 [left, right] 表示当前正在检查的一段连续子串。

#3. 窗口或区间维护规则

每次 right 向右移动一位，把 s[right] 作为新字符加入窗口。

如果 s[right] 之前出现过，设它上一次出现的位置是 lastIndex：

• 如果 lastIndex >= left，说明重复字符还在当前窗口内，需要把 left 移动到 lastIndex + 1。
• 如果 lastIndex < left，说明旧字符已经不在当前窗口内，不需要移动 left。

这两个情况可以统一写成：

left = Math.max(left, lastIndex + 1);

处理完当前字符后，再把 s[right] 的最近出现位置更新为 right。

#4. 答案更新时机

本题求最长合法窗口。

每次处理完重复字符后，窗口 [left, right] 一定是不含重复字符的合法窗口，所以此时用窗口长度更新答案：

ans = Math.max(ans, right - left + 1);

注意：答案要在窗口重新合法后更新，不能在发现重复但还没调整 left 时更新。

#5. 边界条件与易错点

边界条件：

• 如果 s 是空字符串，循环不会执行，最终返回初始值 0。
• 如果 s 只有一个字符，窗口长度最大为 1。
• 如果所有字符都不重复，left 不移动，答案就是 s.length。
• 如果所有字符都相同，窗口长度始终会被压缩到 1。

易错点：

不要直接写成：

left = lastIndexMap.get(char) + 1;

因为重复字符上一次出现的位置可能已经在窗口左侧，直接赋值会导致 left 回退。

例如 s = "abba"：

• 遍历到第二个 b 时，窗口左边界移动到下标 2。
• 继续遍历到最后一个 a 时，旧的 a 在下标 0，已经不在当前窗口内。
• 如果直接把 left 改成 1，窗口会错误变成 "bba"。

所以 left 必须只能向右移动，不能回退。

#6. 代码实现

// 思路1
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const lastIndexMap = new Map();
  let left = 0;
  let ans = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    if (lastIndexMap.has(char)) {
      left = Math.max(left, lastIndexMap.get(char) + 1);
    }

    lastIndexMap.set(char, right);
    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

// 思路2
var lengthOfLongestSubstring = function (s) {
  const hash = new Set();
  let result = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const current = s[right];
    while (hash.has(current)) {
      hash.delete(s[left++]);
    }
    hash.add(current);
    result = Math.max(result, right - left + 1);
  }
  return result;
};

#7. 复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。right 从左到右遍历一次，left 也只会向右移动，不会回退。
• 空间复杂度：O(min(n, m))，其中 m 是字符集大小。lastIndexMap 最多记录出现过的字符最近下标。