无重复字符的最长子串

一、题目（LeetCode 3 · 中等 · Hot100）

给定字符串 s，找出不含有重复字符的最长子串（连续）的长度。

输入：s = "abcabcbb"
输出：3      // 最长子串 "abc"

输入：s = "abba"
输出：2      // 最长子串 "ab" 或 "ba"

二、思路演进

2.1 暴力：枚举所有子串再查重

O(n²) 个子串，每个 O(n) 查重，O(n³)；用 HashSet 边扩边查可以压到 O(n²)，仍不够。

2.2 关键洞察一：滑窗——左右指针都只前进

无重复性有单调性：若 s[l..r] 无重复，它的任意子串也无重复；若 s[l..r] 已重复，再向右加长只会更糟。

于是右指针每轮扩张一格；一旦新字符在窗口内重复，左指针向右吐字符直到恢复合法。左、右各自从 0 走到 n-1、全程不回退——"最多 2n 次操作"就是 O(n) 的来源。窗口 [l, r] 始终维持"当前无重复"这个不变量，答案取过程中最大窗宽。

2.3 关键洞察二：记最后出现位置，左指针跳着走

Set 版左指针一格一格吐，没必要。记 last[c] 为字符 c 最近一次出现的下标。新字符 c 重复（即 last[c] >= left，重复者还在窗口里）时，left 直接跳到 last[c] + 1。一步跨过中间所有字符——它们反正都会被吐掉。

注意 left 只能前进。"abba" 走到第二个 a 时 last[a]+1 = 1，但 left 已经因第二个 b 推进到 2。直接赋值会让窗口倒退、把重复的 b 又包进来。

三、复杂度分析

• 时间 O(n)：right 走 n 步。left 在两种版本里都单调不回退（Set 版逐格前进，跳跃版一步到位），合计至多 n 步 → 总计 O(2n)。
• 空间 O(min(n, 字符集))：本题可见 ASCII，即 O(128) 常数；Unicode 场景换成 HashMap 则为 O(不同字符数)。

四、代码

package org.example;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_3 {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
        System.out.println(lengthOfLongestSubstring("abba"));     // 2，跳跃版的试金石
        System.out.println(lengthOfLongestSubstring(" "));        // 1，空格也是字符
    }

    /** 版本一：Set 维护窗口，右进左吐，逻辑最直观 */
    public static int lengthSet(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            while (window.contains(c)) {       // 吐到不再含 c 为止
                window.remove(s.charAt(left));
                left++;
            }
            window.add(c);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    /** 版本二（主推）：记录最后出现位置，左指针直接跳 */
    public static int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last[c] >= left) {             // 重复字符还躺在窗口内
                left = last[c] + 1;            // 跳到它身后；left 天然只前进
            }
            last[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

}

五、坑点

• "abba" 是试金石：跳跃版若不判 last[c] >= left 而直接 left = last[c]+1，第二个 a 会把 left 拉回 1，窗口混进两个 b，输出 3 而不是 2。
• 子串 ≠ 子序列："无重复子序列"的最长长度就是不同字符数（每个取一次），面试口头追问常用来筛概念。
• 每轮都更新 best：窗口合法性与 best 更新在每轮末尾做，不要只在"发生重复"时记录。
• 空格是合法字符：" " 的答案是 1；"" 是 0，上述循环天然覆盖，无需特判。
• 存 last 用 int[128] 依赖"可见 ASCII"的题目约束，Unicode 要换 HashMap<Character, Integer>——被问到时能主动切换。

六、变形追问

• 变体一（至多 K 个不同字符的最长子串，LeetCode 340；K=2 即 LeetCode 159）：窗口合法性从"无重复"换成"不同字符 ≤ K"。计数 HashMap + 当前种类数，右进超过 K 种就左吐，模板几乎不变。姊妹篇见 找到字符串中所有字母异位词。
• 变体二（输出子串本身而非长度）：记录 best 被刷新时的 right。回推 left = right - best + 1 再 substring——考察的是"滑窗过程中如何携带答案的现场信息"。

2026-10 新增（E 轨 · Hot100 第一批）。