最长无重复字符子串

问题

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

示例：

• 输入 "abcabcbb"，输出 3（"abc"）
• 输入 "bbbbb"，输出 1（"b"）
• 输入 "pwwkew"，输出 3（"wke"）

解答

滑动窗口解法

/**
 * 求最长无重复字符子串的长度
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  // 记录字符最后出现的位置
  const map = new Map();
  let maxLen = 0;
  // 窗口左边界
  let left = 0;

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

    // 如果字符已存在且在窗口内，移动左边界
    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }

    // 更新字符位置
    map.set(char, right);
    // 更新最大长度
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

// 测试
console.log(lengthOfLongestSubstring('abcabcbb')); // 3
console.log(lengthOfLongestSubstring('bbbbb'));    // 1
console.log(lengthOfLongestSubstring('pwwkew'));   // 3
console.log(lengthOfLongestSubstring(''));         // 0
console.log(lengthOfLongestSubstring('abba'));     // 2

返回子串本身

/**
 * 返回最长无重复字符子串
 * @param {string} s
 * @return {string}
 */
function longestSubstring(s) {
  const map = new Map();
  let maxLen = 0;
  let left = 0;
  let start = 0; // 记录最长子串的起始位置

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

    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }

    map.set(char, right);

    // 更新最大长度和起始位置
    if (right - left + 1 > maxLen) {
      maxLen = right - left + 1;
      start = left;
    }
  }

  return s.slice(start, start + maxLen);
}

// 测试
console.log(longestSubstring('abcabcbb')); // "abc"
console.log(longestSubstring('pwwkew'));   // "wke"

关键点

• 滑动窗口：右指针遍历，左指针按需收缩
• 用 Map 记录字符最后出现的索引，O(1) 判断重复
• 遇到重复字符时，左边界跳到重复字符的下一位
• 注意判断重复字符是否在当前窗口内（map.get(char) >= left）
• 时间复杂度 O(n)，空间复杂度 O(min(n, m))，m 为字符集大小