夜雨聆风3. 无重复字符的最长子串
题目很简洁：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。子串要求字符在原字符串中连续。
举几个例子：
输入 s = "abcabcbb"，输出 3。无重复字符的最长子串是 "abc"，长度为 3。注意 "bca"、"cab" 也都是合法答案，长度同样是 3。
输入 s = "bbbbb"，输出 1。所有字符都是 b，无重复的最长子串只能是单个 "b"。
输入 s = "pwwkew"，输出 3。最长子串是 "wke"，长度为 3。这里要强调，"pwke" 是子序列而非子串（中间跳过了一个 w），不能算作答案。
这类"在连续区间内维护某种约束"的问题，标准武器就是滑动窗口：用左右两个指针框定一个窗口，右指针不断扩张纳入新字符，一旦窗口内出现重复就收缩左指针，过程中记录窗口能达到的最大长度。
第一种：滑动窗口 + 字符串切片（易懂但超时）
最贴近"窗口"字面含义的实现，是直接维护一个表示当前窗口内容的字符串 window。右指针每遇到一个新字符，就判断它是否已经在窗口里：如果不在，直接追加并更新最大长度；如果在，就把左边界跳到那个重复字符的下一位，重新截取窗口。
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
left = 0
longest = 0
window = ''# 当前无重复字符的窗口内容
for right in range(len(s)):
cur_char = s[right]
if cur_char notin window:
window += cur_char
longest = max(longest, len(window))
else:
# 找到重复字符在窗口内的位置，左边界跳到它的下一位
dup_index = window.find(cur_char)
left = left + dup_index + 1
window = s[left:right + 1]
return longest
window 始终维护当前窗口里的字符。遇到新字符时，若不重复就追加进窗口并刷新 longest；若重复，则用 window.find(cur_char) 定位重复字符在窗口内的下标，把左边界 left 推进到该字符的下一位，再用切片重新得到新窗口。
这种写法直观、容易理解，但缺点也比较明显：cur_char not in window、window.find(...) 以及 s[left:right+1] 切片这几个操作，每次都需要遍历窗口字符串，最坏情况下单步就是 O(n)，整体时间复杂度退化到 O(n²)。
时间复杂度 O(n²)，空间复杂度 O(n)（窗口字符串）。
第二种：滑动窗口 + 哈希表（推荐写法）
要把时间复杂度降到 O(n)，关键是去掉每一步里对窗口的线性扫描。可以用一个哈希表记录每个字符最近一次出现的下标，这样判重和定位都能 O(1) 完成，不再需要切片和 find。
具体做法是：右指针 right 遍历字符串，对每个字符 cur_char，如果它在哈希表里、且上次出现的位置在当前窗口左边界 left 之内（即 >= left），就把 left 直接跳到那个位置的下一位；然后更新该字符的最新下标，并用 right - left + 1 计算当前窗口长度刷新答案。
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
last_seen = {} # 字符 -> 最近一次出现的下标
left = 0
longest = 0
for right, cur_char in enumerate(s):
# 若该字符在窗口内出现过，收缩左边界到重复位置的下一位
if cur_char in last_seen and last_seen[cur_char] >= left:
left = last_seen[cur_char] + 1
last_seen[cur_char] = right
longest = max(longest, right - left + 1)
return longest
这里有个容易写错的细节：判断重复时，不能只看字符是否在哈希表里，还必须确认它上次出现的位置落在当前窗口内（last_seen[cur_char] >= left）。因为哈希表记录的是字符的历史下标，某个字符可能在很早以前出现过、但早已被移出窗口，这种情况不应该再收缩左边界。加上这层判断，才能保证 left 只会向右移动、不会回退。
整个过程中，right 从头到尾扫一遍，left 单调向右推进，每个字符的入表、查表都是 O(1)，因此总时间复杂度是线性的。
时间复杂度 O(n)，空间复杂度 O(min(n, m))，其中 m 为字符集大小（哈希表最多存储字符集大小个字符）。
两种解法都基于滑动窗口的框架，差别在于窗口状态的维护方式：切片写法直接保存窗口子串、直观但每步隐含 O(n) 扫描；哈希表写法用"字符 → 最新下标"把判重和收缩都压到 O(1)，整体达到 O(n)。
