无重复字符的最长子串

    字符串 滑动窗口 哈希表

    题目描述

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

    例如：

    • 输入 "abcabcbb"，输出 3（最长子串为 "abc"）。
    • 输入 "bbbbb"，输出 1（最长子串为 "b"）。
    • 输入 "pwwkew"，输出 3（最长子串为 "wke"）。

    思路分析

    从暴力开始思考

    面对这道题，最直接的想法是：枚举所有可能的子串，检查每个子串是否包含重复字符，记录满足条件的最长长度。

    具体做法是用两层循环确定子串的起始位置 i 和结束位置 j，再用一个 isUnique 辅助函数借助 Set 检查 s[i..j] 内是否存在重复字符。这个思路正确，代码也易于理解，但代价很高——两层循环加上内部的 isUnique 遍历，时间复杂度达到 O(n³)，面对较长字符串时会超时。

    暴力解的问题在于大量的重复工作：每次检查 s[i..j] 是否无重复，都从头扫描，完全不利用上一次检查的结果。

    用滑动窗口消除重复工作

    注意到一个关键性质：如果 s[i..j] 是无重复子串，那么 s[i..j-1] 一定也是无重复子串。反过来，当右边界 right 引入了一个重复字符时，我们只需要把左边界 left 向右收缩，直到窗口内不再有重复为止——不必重新扫描整个区间。

    这就是滑动窗口的核心：用双指针维护一个始终无重复的窗口，right 不断向右扩张，left 按需向右收缩，在此过程中记录窗口的最大长度。

    Set 版滑动窗口使用 Set 存储当前窗口内的字符。每次 right 向右移动时：

    • 若 s[right] 不在 Set 中，直接加入，更新最大长度，right++。
    • 若 s[right] 已在 Set 中，说明窗口内有重复，从左侧删除 s[left] 并令 left++，反复执行直到重复消失，再将 s[right] 加入。

    这样左右指针各自只向右走一次，时间复杂度降至 O(n)。

    用 Map 记录位置，让左指针直接跳跃

    Set 版本在遇到重复时需要逐个从左侧删除字符，左指针可能走好几步才能消除重复。能否更快？

    关键在于：当 s[right] 是重复字符时，我们真正需要的是"把左指针移到上一次 s[right] 出现位置的右边一格"，而不是一步步地移。如果用 Map 记录每个字符最后出现的下标，就能在 O(1) 内得到这个位置，让 left 直接跳过去。

    Map 版（优化）滑动窗口的逻辑如下：

    • 用 indexMap 存储 字符 → 最后出现的下标。
    • 每次处理 s[right]：若 indexMap 中已有该字符的记录，令 left = Math.max(left, indexMap.get(char) + 1)。之所以取 Math.max，是为了防止左指针向左倒退——indexMap 中存的是历史位置，如果该字符上次出现在当前窗口的左边界之外，就不应该移动 left。
    • 然后更新 indexMap.set(char, right)，刷新该字符的最新位置，再计算当前窗口长度更新 maxLen，最后 right++。

    这样右指针依然只走一遍，但左指针不再逐步移动，而是每次直接跳到目标位置。从分析角度看，两者时间复杂度同为 O(n)，但 Map 版减少了左指针的移动次数，实际运行往往更快。

    三种方案对比

    暴力枚举Set 滑动窗口Map 优化滑动窗口
    时间复杂度O(n³)O(n)O(n)
    空间复杂度O(min(n, m))O(min(n, m))O(min(n, m))
    左指针移动—逐步收缩直接跳跃
    适用场景理解题意思路清晰，易实现性能优先

    示例代码

    暴力枚举
    Set 滑动窗口
    Map 优化滑动窗口
    /**
 * 使用蛮力方法找到字符串中最长不重复子字符串的长度
 *
 * 算法思路：
 * - 双层循环遍历所有可能的子字符串
 * - 对每个子字符串检查是否所有字符都不重复
 * - 记录满足条件的最长子字符串长度
 *
 * 时间复杂度：O(n³)
 * 空间复杂度：O(min(n, m)) - m为字符集大小，存储在 Set 中
 *
 * @param str - 输入字符串
 * @returns 最长不重复子字符串的长度
 */
export function lengthOfLongestSubString(str: string): number {
    // 获取字符串长度，用于循环边界
    const n = str.length;
    // 用来存储找到的最长不重复子字符串的长度
    let maxLen = 0;

    // 外层循环：设置子字符串的起始位置 i
    for (let i = 0; i < n; i++) {
        // 内层循环：设置子字符串的结束位置 j
        for (let j = i; j < n; j++) {
            // 检查从位置 i 到 j 的子字符串是否所有字符都不重复
            if (isUnique(str, i, j)) {
                // 如果不重复，计算当前子字符串长度 (j - i + 1)，并更新最大值
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    // 返回最长不重复子字符串的长度
    return maxLen;
}

/**
 * 检查字符串在指定范围内是否所有字符都不重复
 *
 * 算法思路：
 * - 使用 Set 来跟踪已经见过的字符
 * - 遍历指定范围内的每个字符
 * - 如果遇到重复字符，立即返回 false
 * - 否则将字符加入 Set 中继续检查
 *
 * 时间复杂度：O(n) - n为检查范围的大小
 * 空间复杂度：O(n) - Set 最多存储 n 个字符
 *
 * @param s - 输入字符串
 * @param left - 检查范围的起始位置（包含）
 * @param right - 检查范围的结束位置（包含）
 * @returns 如果范围内所有字符都不重复返回 true，否则返回 false
 */
export function isUnique(s: string, left: number, right: number): boolean {
    // 创建一个 Set 用来存储已经见过的字符
    const set = new Set();
    // 遍历从 left 到 right（包含）的所有字符
    for (let i = left; i <= right; i++) {
        // 检查当前字符是否已经存在于 Set 中
        if (set.has(s[i])) {
            // 如果字符已存在，说明有重复，返回 false
            return false;
        }
        // 如果字符不存在，将其添加到 Set 中
        set.add(s[i]);
    }
    // 如果遍历完所有字符都没有发现重复，返回 true
    return true;
}

    复杂度分析

    • 时间复杂度：O(n)，其中 n 是字符串长度。右指针遍历整个字符串一次，左指针（在 Map 版中）同样最多向右移动 n 次，整体线性。
    • 空间复杂度：O(min(n, m))，其中 m 是字符集大小（如 ASCII 为 128）。Set/Map 最多存储窗口内不重复的字符数量，不会超过字符集大小。

    示例演示

    以 s = "abcabcbb" 为例，演示 Map 优化滑动窗口的执行过程：

    步骤rights[right]left 变化当前窗口maxLen
    10a0 → 0"a"1
    21b0 → 0"ab"2
    32c0 → 0"abc"3
    43a0 → 1（a 上次在 0）"bca"3
    54b1 → 2（b 上次在 1）"cab"3
    65c2 → 3（c 上次在 2）"abc"3
    76b3 → 5（b 上次在 4）"cb"3
    87b5 → 7（b 上次在 6）"b"3

    最终返回 3。

    注意第 7 步：b 上次出现在下标 4，left 从 3 直接跳到 5，跳过了逐步收缩的过程，这正是 Map 版相对 Set 版的优势所在。