无重复字符的最长子串

题意

给定字符串 s，找出不含重复字符的最长子串的长度。

思路

枚举所有子串 O(n²) 会超时。滑动窗口优化：右指针扩展，当遇到重复字符时，左指针直接跳到该字符上次出现位置 + 1，保证窗口始终无重复。

用一个数组 last[128] 记录每个字符上次出现的位置（1-indexed）。右指针移动时，左指针取 max(左指针, last[当前字符])，然后更新 last。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * Author by Rainboy
 */
// main.cpp：滑动窗口，char->last_pos 跳跃，O(n)。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[128] = {}, l = 0, ans = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            l = max(l, last[s[r]]);
            ans = max(ans, r - l + 1);
            last[s[r]] = r + 1;
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << Solution().lengthOfLongestSubstring(s) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/usr/bin/env python3
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        l = ans = 0
        for r, ch in enumerate(s):
            if ch in last:
                l = max(l, last[ch] + 1)
            ans = max(ans, r - l + 1)
            last[ch] = r
        return ans


def main() -> None:
    s = input().strip()
    print(Solution().lengthOfLongestSubstring(s))


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n)，每个字符被左右指针各访问一次。
空间复杂度：O(|Σ|)，字符集大小（ASCII 128）。

总结

"记录每个元素上次位置，遇到重复时跳跃左指针"是滑动窗口的一种变体，相比每次移动左指针一格的写法更高效。关键在于左指针只向前移动，不回退。

无重复字符的最长子串

目录

题意

思路

代码

复杂度

总结