Description

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = “abcabcbb”

Output: 3

Explanation: The answer is “abc”, with the length of 3.

Note that “bca” and “cab” are also correct answers.

Example 2:

Input: s = “bbbbb”

Output: 1

Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: s = “pwwkew”

Output: 3

Explanation: The answer is “wke”, with the length of 3.

Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

暴力解法

最直接的方法是枚举所有子串并检查是否重复。

但检查一个子串是否有重复要 O(n)，枚举子串又要 O(n^2)，
总复杂度 O(n^3)，无法应对长字符串。

Solution

优化思路

我们希望避免重复扫描。
核心思想是：维持一个“无重复”的滑动窗口，
随着字符串的扫描动态扩展和收缩。

窗口可以用两个指针表示：

• left：窗口左边界
• right：窗口右边界

从左到右遍历字符串，每次将s[right]加入窗口。
如果窗口出现重复字符，就移动 left 指针，直到窗口重新变得无重复。

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
29

#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        unordered_set<char> charSet; // 记录窗口中的字符
        int left = 0;

        for (int right = 0; right < n; right++) {
            // 如果当前字符在窗口中已存在
            while (charSet.count(s[right])) {
                // 移除窗口左侧字符，直到 s[right] 可加入
                charSet.erase(s[left]);
                left++;
            }
            // 将当前字符加入窗口
            charSet.insert(s[right]);

            // 更新最大长度
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

关键逻辑

1
2
3
4
5

while (charSet.count(s[right])) {
    charSet.erase(s[left]);
    left++;
}
charSet.insert(s[right]);

当s[right]已在窗口中出现过，就会导致重复。于是通过 while 循环，不断从左边移除字符：

• 每次erase(s[left]) 相当于收缩窗口。
• 直到s[right] 不再重复，循环才结束。
• 最后再插入s[right]，此时窗口重新变得“无重复”。

这里的关键点是：

我们并不关心被移除的字符是谁，
唯一的目标是让s[right]能安全加入集合。

Sliding Window

滑动窗口其实是“固定或可变长度的区间扫描”的思维模型。
它的核心是：用空间换时间，避免重复计算。

• 最常见的字符串处理类：动态维护一个子串或子序列。
• 数组 / 序列分析：窗口表示一段连续数据。通常不关心字符，而关心数值区间。