不重复最大子串

给定一个字符串，请实现一个函数来找到其中的不重复最大子串。例如，对于字符串"abcabcbb"，不重复最大子串是"abc"，长度为3。

• 请写出实现该功能的代码，并说明其时间复杂度。
• 考虑到性能优化，你认为还有哪些改进空间？请提出优化思路并实现优化后的代码。

参考答案：

一、滑动窗口实现

function lengthOfLongestSubstring(s) {
  let set = new Set();
  let left = 0, maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

// 测试
console.log(lengthOfLongestSubstring("abcabcbb")); // 输出 3

思路

• 使用 滑动窗口 [left, right] 遍历字符串。
• 用 Set 存储当前窗口内字符。
• 当遇到重复字符时，移动左指针，直到窗口内无重复字符。
• 每次窗口扩大时更新最大长度。

时间复杂度

• 每个字符 最多进出窗口一次 → O(n)
• 空间复杂度：O(min(n, Σ))，Σ 是字符集大小。

---

二、性能优化

上面方法每遇到重复字符，需要 逐个删除左边字符。可以进一步优化为 直接跳过重复字符的索引，使用 Map 存储字符上次出现的索引。

优化实现（使用 Map）

function lengthOfLongestSubstringOptimized(s) {
  const map = new Map();
  let maxLen = 0, left = 0;

  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      left = map.get(s[right]) + 1; // 直接跳过重复字符
    }
    map.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

// 测试
console.log(lengthOfLongestSubstringOptimized("abcabcbb")); // 输出 3

优化说明

• 直接跳过重复字符，减少了删除操作。
• 对比 Set 方法，尤其在遇到长重复序列时性能更好。
• 时间复杂度仍然是 O(n)，但常数时间更低。
• 空间复杂度 O(min(n, Σ))，Σ 是字符集大小。

题目要点：

1. 滑动窗口 是解决最长不重复子串问题的核心思想。
2. Set 方法简单直观，但每遇到重复字符可能多次移动左指针。
3. Map 优化通过记录字符索引，直接跳过重复区域，减少不必要操作。
4. 时间复杂度 O(n)，空间复杂度 O(Σ)。