3. Longest Substring Without Repeating Characters

题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

大意

找出最长的连续的没有重复元素的子字符串。

答案

class Solution {
public:
 int lengthOfLongestSubstring(string s) {
        int len  =s.size();
        if(len==1) return 1;
        int res =1;
        int maxres =0;
        int left =0;
        int right=1;
        unordered_set<int> charset;
        charset.insert(s[left]);
        while(right<len)
        {
            if(charset.count(s[right])!= 0)
            {
                charset.erase(s[left]);   
                left++;
            }
            else
            {  
                charset.insert(s[right]);
                right++;
                res = right -left;
                maxres =max(maxres,res);
            }
        }
        return maxres;
    }
};

思路

此问题是求最长的连续子字符串，可以使用滑动窗口算法求解。

维护左右两个指针，设下标left和right，[left, right ) 表示一个窗口，不断的滑动窗口。

不断的滑动右边的窗口：

当s[right] 和窗口内的字符有重复时，则不断的滑动左边的窗口，直到把重复的字符滑出维护的窗口，这种情况下，窗口的值是越来越小的。

当s[right]和窗口内的字符没有重复时，则不断的滑动右边的窗口，

当右边的窗口到达字符串的最后时，就是循环结束的时候了。

判断存在

c++中判断存在用 charset.count(number)!=0来判断在charset这个set中，number不存在。