无重复字符的最长子串

描述

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

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这题变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。

唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

C++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 定义一个哈希表，用于记录窗口中每个字符出现的次数
        unordered_map<char, int> window;
        // 定义左右指针，以及结果变量
        int left = 0, right = 0;
        int res = 0;
        // 右指针向右移动，直到字符串末尾
        while(right < s.size()){
            // 取出右指针所指向的字符，并将右指针向右移动一位
            char c = s[right];
            right++;
            // 更新哈希表中的字符出现次数
            window[c]++;
            // 如果窗口中出现了重复字符，移动左指针，直到窗口中不再有重复字符
            while(window[c] > 1){
                char d = s[left];
                left++;
                window[d]--;
            }
            // 更新结果变量
            res = max(res, right - left);
        }
        // 返回结果
        return res;
    }
};