LeetCode 第 3 题《无重复字符的最长子串》是滑动窗口思想的另一个经典变种——不定长滑动窗口。它考察的是如何在满足特定条件（无重复）下，动态地扩展和收缩窗口以找到最优解。这在竞赛中是解决一系列“最长/最短满足条件的连续子数组/子串”问题的通用模型。

---

第一部分：题目描述

题目名称： 无重复字符的最长子串 (Longest Substring Without Repeating Characters) 输入文件： substring.in 输出文件： substring.out 时间限制： 1.0 s 空间限制： 256 MB

【题目描述】

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

定义说明：

1. 子串 (Substring)：字符串中必须是连续的一段字符序列。
2. 不含重复字符：指子串中的每个字符最多只出现一次。

【输入格式】

输入文件包含一行，一个字符串 $S$。

【输出格式】

输出一行，包含一个整数，表示最长不含重复字符的子串的长度。

【输入样例 1】

abcabcbb

【输出样例 1】

3

(说明：最长无重复子串是 "abc"，其长度为 3。)

【输入样例 2】

bbbbb

【输出样例 2】

1

(说明：最长无重复子串是 "b"，其长度为 1。)

【输入样例 3】

pwwkew

【输出样例 3】

3

(说明：最长无重复子串是 "wke"，其长度为 3。请注意答案必须是子串，"pwke" 是一个子序列，不是子串，因此是无效的。)

【数据范围与提示】

• $0 \le |S| \le 5 \times 10^4$
• $S$ 可能由英文字母、数字、符号和空格组成 (即标准 ASCII 字符)。

---

第二部分：教练辅导时间

1. 思路提示 (Hint)

• 思考点 1 (暴力法)：最直观的想法是什么？是不是可以枚举所有的子串，然后逐个判断它们是否含有重复字符？这个方法可行吗？它的时间复杂度会是多少？（提示：枚举起点和终点需要 $O(N^2)$，每次判断又需要时间...）
• 思考点 2 (优化)：暴力法的瓶颈在于大量的重复计算。当我们检查完 "abc"，再检查 "abca" 时，我们其实已经知道 "abc" 是合法的。当 a 出现重复时，我们能否不从头开始，而是只做必要的调整？
• 思考点 3 (滑动窗口)：想象一个“窗口”在字符串上滑动。我们用一个指针 right 不断向右扩大窗口，同时用另一个指针 left 在必要时向右收缩窗口。
  • 扩大：当新进入的字符 S[right] 在当前窗口中不存在时，我们可以安全地扩大窗口。
  • 收缩：当新进入的字符 S[right] 在当前窗口中已存在时，说明窗口不合法了。我们必须从左边开始收缩窗口（即 left++），直到把那个重复的旧字符移出窗口为止。

2. 预备知识点 (Prerequisites)

• 滑动窗口 (Sliding Window)：特别是不定长窗口的模型。窗口的大小是根据条件动态变化的。
• 哈希表/计数数组：为了能在 $O(1)$ 的时间内判断一个字符是否已在当前窗口内，我们需要一个高效的数据结构。
  • 对于 ASCII 字符集，可以直接用一个大小为 128 的布尔或整型数组 (bool seen[128]) 作为哈希表，速度最快。
  • 对于更通用的字符集，可以使用 std::unordered_set 或 std::map。
• 双指针 (Two Pointers)：left 和 right 指针是实现滑动窗口的具体工具。

3. 启发式教学与草稿纸推演 (Heuristic Approach)

来，拿出草稿纸，我们画图模拟一下不定长滑动窗口。

场景设置：

• $S = \text{"pwwkew"}$
• 变量：left=0, right=0, maxLength=0, window_chars (一个哈希集合)

推演步骤：

right	S[right]	window_chars 状态	操作	left	窗口内容	窗口长度	maxLength
0	'p'	{}	p不在，加入	0	"p"	1
1	'w'	{'p'}	w不在，加入		"pw"	2	2
2		{'p','w'}	w存在！ 1. 从左边移除S[left]('p') 2. left++ 3. S[left]还是w，继续移除 4. left++ 5. 加入新w	2	"w"	1
3	'k'	{'w'}	k不在，加入		"wk"	2
4	'e'	{'w','k'}	e不在，加入		"wke"	3	3
5	'w'	{'w','k','e'}	w存在！ 1. 从左边移除S[left]('w') 2. left++ 3. 加入新w	3	"kew"		3

复杂度分析思考过程：

• 时间复杂度： 看看 left 和 right 指针。right 指针从头到尾遍历了一遍字符串 $S$，left 指针也只从头到尾走了一遍。每个字符最多被 right 访问一次，被 left 访问一次。所以总的操作次数是线性的，即 $O(N)$。
• 空间复杂度： 我们使用了一个哈希集合（或数组）来存储窗口内的字符。在最坏的情况下，如果字符串所有字符都不同，那么窗口会扩大到整个字符串。空间复杂度取决于字符集的大小。对于 ASCII，它是 $O(128)$，即 $O(1)$ 或 $O(\Sigma)$。

---

第四部分：伪代码提示 (NOI/CSP风格)

// 伪代码提示：无重复字符的最长子串
// 帮助你构建代码框架，但不提供完整实现

// 1. 初始化
// left 指针，指向窗口左边界
int left = 0;
// max_len，记录全局最大长度
int max_len = 0;
// 哈希表，记录窗口内已有的字符。可以用 bool visited[128] = {false};
// 或者用一个更通用的数据结构如 set 或 map

// 2. 主循环
// right 指针，作为主循环变量，不断向右扩展窗口
for (int right = 0; right < S.length(); ++right) {
    char char_in = S[right]; // 即将进入窗口的字符

    // 3. 处理重复字符 (收缩窗口)
    // while (char_in 在哈希表中已存在) {
    //     char char_out = S[left]; // 即将离开窗口的字符
    //     // 从哈希表中移除 char_out
    //     // left 指针向右移动
    //     left++;
    // }
    
    // 4. 将新字符加入窗口
    // 将 char_in 加入哈希表

    // 5. 更新最大长度
    // 当前窗口长度为 right - left + 1
    // max_len = max(max_len, right - left + 1);
}

// 6. 输出结果
// print(max_len);

教练提示： 这个伪代码框架是解决这类问题的通用模板。请仔细理解每一步的作用，特别是 while 循环收缩窗口的逻辑，这是滑动窗口算法的精髓所在。尝试用这个框架去解决其他类似的 “最长/最短连续子串” 问题。加油！