yicong@algo:~/code/03-sliding-window$ cat 0003-longest-substring-without-repeating-characters.cpp
3. 无重复字符的最长子串
// 思路
滑动窗口不变量:[left, right] 闭区间内字符互不重复。 right 从左到右扫描,每读入一个新字符 s[right]: - 若已存在于窗口(unordered_set 中),说明 left 需要右移收缩窗口, 不断去掉 s[left] 直到 s[left] == s[right](即重复的那个字符被移出), 再把 left+1 跳过它,此时窗口重新满足无重复。 - 若不存在,直接加入窗口,更新 ans = max(ans, right-left+1)。 关键:left 只增不减,每个字符最多被访问两次(一次入窗口,一次出窗口), 故时间复杂度 O(n)。unordered_set 最多存窗口内字符,字符集有限(ASCII 128), 故空间 O(min(n, 字符集)) = O(n) 最坏,但常数很小。
// 时间复杂度
O(n),每个字符最多入、出窗口各一次
// 空间复杂度
O(min(n, 字符集)),unordered_set 最大存一整个窗口的字符
// 易错点
- left 不回退:若用 if 而非 while,left 可能停在重复字符左边; - 空串:right 循环不进入,直接返回 ans=0,正确; - char 有符号(-128~127),直接做数组下标需转 unsigned char; - 答案在插入前更新:对于 "abca",right=3 时 left=1,窗口长 3,正确; 若在 left 收缩完再更新,则 "abca" 在 right=2 时 ans=3 已记录; - 收缩时 s[left] != s[right] 的判断不能省,否则会把非重复字符也漏删。
// 面试口述要点
- 先说暴力 O(n³) 或哈希集合的朴素滑动窗口 O(n²); - 引出优化点:遇到重复时不用逐个删,而是直接把 left 跳到重复字符右侧; - 进一步优化:用数组记录每个字符上次出现的下标,right 扩张时直接 max(left, last+1), 做到真正的 O(n)/O(1)(无需 set,无需 while 收缩循环),面试常见扩展。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:unordered_set 滑动窗口(你的写法)
// right 扩张,发现重复时 while 收缩,代码直观。
// ================================================================
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int ans = 0;
int left = 0;
for (int right = 0; right < (int)s.size(); ++right) {
if (window.count(s[right])) {
while (s[left] != s[right]) {
window.erase(s[left]);
++left;
}
++left; // 跳过重复字符本身
} else {
window.insert(s[right]);
ans = max(ans, right - left + 1);
}
}
return ans;
}
// ================================================================
// 版本二:数组记录上次出现位置,O(n)/O(1),面试更优写法
// 核心:遇到字符 c,上次出现位置为 last[c]。
// left 必须跳到 max(left, last[c]+1),跳过整个旧出现到当前位置之间所有字符。
// 无需 set,无需 while 收缩,每次 right 只移动一次。
// ================================================================
int lengthOfLongestSubstring_v2(string s) {
vector<int> last(128, -1);
int left = 0, ans = 0;
for (int right = 0; right < (int)s.size(); ++right) {
unsigned char c = s[right]; // 有符号 char 转下标避免越界
left = max(left, last[c] + 1); // 跳过 c 上次出现的位置
last[c] = right; // 更新 c 最近出现位置
ans = max(ans, right - left + 1);
}
return ans;
}
};
// 本地测试:输入一行字符串(可含空格);输出最长无重复子串长度
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if (!getline(cin, s)) return 0;
cout << Solution().lengthOfLongestSubstring(s) << '\n';
return 0;
}