题目描述

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

样例

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

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

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

算法

(双指针) $O(n)$

1. 使用滑动窗口维护一个没有重复字符的区间
2. 哈希表$window$存放区间中字符的出现次数
3. 若新加入的字符不会改变区间性质，则扩张区间右端点；否则收缩左端点，直到区间性质恢复
4. 每一轮的扩张/收缩操作都要更新一次答案

时间复杂度

由于扩张/收缩操作最多$n$次（$n$为字符串长度），因此时间复杂度为$O(n)$

C++ 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int l = 0, r = 0, ret = 0;
        while (r < s.size()) {
            char c = s[r ++ ];
            window[c] ++ ;
            while (window[c] > 1) window[s[l ++ ]] -- ;
            ret = max(ret, r - l);
        }
        return ret;
    }
};