📝 题目描述

题目链接：无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

💡 解题思路

方法一：滑动窗口

要想使用滑动窗口，首先需要想一下暴力的朴素解法是怎样的。
以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

  • 以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
  • 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
  • 以 ab©abcbb 开始的最长字符串为 ab(cab)cbb；
  • 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
  • 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
  • 以 abcab©bb 开始的最长字符串为 abcab(cb)b；
  • 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
  • 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。

可以发现，如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的。这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k​。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 r_k​ 的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r_k​，直到右侧出现了重复字符为止。

这样一来，我们就可以使用「滑动窗口」来解决这个问题了。

滑动窗口的标准写法通常是：“右指针主动走，左指针被动收缩”。

我们初始化左指针 left 和右指针 right 都为 0，也就是都在起始位置。

开始时，我们让右指针不断向右行进，但在遇到每一个字符 s[right] 时，都要先判断字符 s[right] 是否已经在已有的子串中了，因为我们题目要求是无重复字符的最长字串：

  • 如果字符 s[right] 不在已有的子串中，则将其加入字串，判断并更新最长子串长度，右指针 right 右移；
  • 如果字符 s[right] 在已有的子串中，说明遇到了重复，此时开始移动左指针 left，从左边开始右移，以减少子串长度，直到将和 s[right] 相同的字符踢出子串。完成后，再将字符 s[right] 加入字串，判断并更新最长子串长度。

不断重复上面的过程，直到右指针 right 到达了输入字符串的最右端，则结束算法，此时我们记录的最长的子串的长度即为答案。

🔧 代码实现

1、滑动窗口

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> lookup;
        int n = s.length();
        int left = 0;
        int ans = 0;
        
        // right 指针主动向右遍历
        for (int right = 0; right < n; right++) {
            // 当窗口内包含当前字符 s[right] 时，说明有重复
            // left 指针向右缩进，直到把那个重复字符排除
            while (lookup.find(s[right]) != lookup.end()) {
                lookup.erase(s[left]);
                left++;
            }
            
            // 将当前字符加入窗口
            lookup.insert(s[right]);
            
            // 更新最大长度
            // 此时窗口区间是 [left, right]，长度为 right - left + 1
            ans = max(ans, right - left + 1);
        }
        
        return ans;
    }
};

📊 复杂度分析

  • 时间复杂度：O(N)O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
  • 空间复杂度：O(∣Σ∣)O(∣Σ∣)，其中 ΣΣ 表示字符集（即字符串中可以出现的字符），∣Σ∣∣Σ∣ 表示字符集的大小。

🎯 总结

  • 核心思想：学会滑动窗口的模板最重要。