LeetCode-003：无重复字符的最长子串

传送门

很经典的字符串问题。给定一个字符串，返回它最长且无重复字符的子串。

可以很直接的想到一个枚举的做法，两重循环遍历字符串去枚举子串，复杂度略小于O(n²)，但肯定会超时。于是想到滑动窗口。

滑动窗口可以在母串上维护一个检索区间，从而避免因为匹配失败而导致的低效下标回溯操作。

具体来说，如果窗口右端检索到一个重复字符，那么左端收缩，直到不存在重复字符位置。每次滑动结束后维护ans字符串即可。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int ans = -INT_MAX, left = 0;
        unordered_set<char>str;
        if(!n) return 0;

        for(int right = 0; right < n; right++)
        {
            while(str.find(s[right]) != str.end())
            {
                str.erase(s[left]);
                left++;
            }
            ans = max(ans, right - left + 1);
            str.insert(s[right]);
        }

        return ans;
    }
};