考点：滑动窗口

数据规模 n ≤ 10000000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 10000000
• 复杂度门槛：只允许 O(n)：n 到千万量级时线性做法仍可行，但读入效率与常数要压紧；O(n log n) 在此量级已偏紧。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：滑动窗口

本题切入点

最长无重复字符子串：滑动窗口 + 记录每个字符最近出现位置，右指针扩张、左指针仅在冲突时跳到 last[c]+1，O(n) 可扛 1e7 长度。

维护一个连续区间，进一个元素出一个元素，区间内统计量增量更新。

思路框架（滑动窗口 通法 · 非本题专属）

1. 用左右指针确定一个窗口 [l, r]。
2. 右端点右移：把新元素加入窗口统计。
3. 当窗口违反约束（长度超限 / 含重复等）时，左端点右移，把元素移出统计。
4. 在每个合法窗口上更新答案。
5. 统计量用哈希表或计数数组维护，避免每次重算。

实现要点：注意窗口长度是定长还是不定长：定长则区间长度固定为 k，不定长则靠条件收缩。

复杂度：时间 O(n) ｜ 空间 O(字符集/去重元素数)

该范式的通法易错点

• 移出窗口时忘同步更新统计量。
• 窗口长度与下标边界差 1（长度 k 对应 r-l+1）。

对照本题

• 数据规模 n ≤ 10000000，只允许 O(n)：n 到千万量级时线性做法仍可行，但读入效率与常数要压紧；O(n log n) 在此量级已偏紧。

样例解读

样例 1：输入 xY3abxY3c → 输出 6

最长的无重复字符子串为 "abxY3c"（从第4个字符到第9个字符），长度为6。其中每个字符 a, b, x, Y, 3, c 都只出现了一次。

样例 2：输入 aaaaaaa → 输出 1

所有字符都相同，任意长度大于1的子串都包含重复字符，因此最长无重复子串长度为1。