本文由旧博客内容整理迁入。原发布日期未提供，页面日期为本次整理日期。

题目

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

示例

示例 1

1
2
输入：s = "abcabcbb"
输出：3

解释：无重复字符的最长子串是 "abc"，长度为 3。"bca" 和 "cab" 也是正确答案。

示例 2

1
2
输入：s = "bbbbb"
输出：1

解释：无重复字符的最长子串是 "b"，长度为 1。

示例 3

1
2
输入：s = "pwwkew"
输出：3

解释：无重复字符的最长子串是 "wke"，长度为 3。答案必须是子串的长度，"pwke" 是子序列，不是子串。

提示

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

解题思路

这道题是一个很经典的题目。虽然是不定长滑动窗口，但是依旧可以借鉴滑动窗口的思路：“入、更新、出”。

我一开始没想出来，原因是老想用 if/else 做判断，从而忽略了 while。可以用 while 一直判断新加入的 s[i] 是否重复，并不断移动左端点，直到窗口重新满足无重复字符的条件。

C++ 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int>cnt;
        int ans=0;
        int left=0;
        for(int i=0;i<s.size();i++){
            cnt[s[i]]++;
            while(cnt[s[i]]>1){
                cnt[s[left]]--;
                left++;
            }
            ans=max(ans,i-left+1);
        }
        return ans;
    }
};

为什么更新答案用 max，而不是 min？

这里要求的是最长合法子串，所以用 max 比较当前答案和合法窗口的长度。

“缩短窗口不会引入新的重复字符”描述的是合法性的变化；“取最长”描述的是优化目标，两者并不冲突。每次先收缩到合法，再用 max 记录遇到过的最长窗口。

整理说明：原文中“直到重复的窗口到达最小”改为“直到窗口恢复合法”，避免误解为要求最短窗口。