Leetcode, 3 repeatless longest subsequence

3. Longest substring without repeating characters

Medium difficulty 7743 Switch to English to receive dynamic feedback

Given a string  s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .

Example  1:

 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its  The length is  3.

Example 2:

 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

Example 3:

 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  It's a  Subsequence , Not substring .

The method used in this question is to slide the window , use C++ Medium set To maintain the

The main idea of the topic should be , Provide a string , To find the longest string that does not repeat

The general idea should be like this , Provide a window , Continuously insert the elements in the string backwards , Once the inserted element repeats , Just move the starting position of the window forward one bit , Keep recording the size of the window , Find the maximum

The sliding window here is explained by drawing

Here's an example   acdfcf , It's easy to see , The longest substring should （ One of ） This is acdf , The length is 4

You will now a Put it in the window

 

At this time, the maximum length of the string is 1, namely maxsize = 1

  because c There is no repetition in the window , So will c Also insert into the window

  here maxsize = 2 ,d It doesn't appear in the window , So will d Put it in the window

  here maxsize = 3  ,f Do not repeat in the window , take f Insert window

  Family , Here comes the key point ,c Appeared in the window , therefore , We need to move the left side of the window , Until there is no repetition in the window

 

take a Remove window , But if you will c Insert , Or repeat , So we continue to shrink the left side of the window  

 

 

here size = 3 , maxsize = 4,maxsize Do not update

  Now insert f

  There are repeating elements in the window , So start narrowing the window from the left

 

  here size = 2  , maxsize  = 4 , Finally work it out , The longest non repeating substring should be 4

Understand the general idea , Start now coding Well

First, we need to judge the empty string , If the string is empty , Then return directly

  if(s==""){
            return 0;
        }

Do some initialization

        int left =0,right =0;
        int maxsize =0;
        set<char> detect;

Now let's insert the string , When the inserted character does not appear in the sliding window , Just insert it directly , And update maxsize

      if(detect.find(s[right])==detect.end()){
                detect.insert(s[right]);
                if(detect.size()>maxsize){
                    maxsize = detect.size();
                }
            }

It's used here set In container find , Used to find whether there are the same elements in the container , If not, go back to end（ end ）

, If so, return the location of the same element .

When the same element is found , We should now move the left side of the sliding window , Until there is no repetition

        for(right =0;right<s.size();right++){
            while(detect.find(s[right])!= detect.end()){
                detect.erase(s[left]);
                left++;
            }

Finally, put the complete code , I hope I can help you

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s==""){
            return 0;
        }
        int left =0,right =0;
        int maxsize =0;
        set<char> detect;
        for(right =0;right<s.size();right++){
            while(detect.find(s[right])!= detect.end()){
                detect.erase(s[left]);
                left++;
            }
            if(detect.find(s[right])==detect.end()){
                detect.insert(s[right]);
                if(detect.size()>maxsize){
                    maxsize = detect.size();
                }
            }
        }
        return maxsize;
    }
};