Leetcode hot topic Hot 100 - ＞ 3. longest substring without repeated characters

Description of the stem ：

Given a string s , Please find out There are no duplicate characters Of   Longest substrings   The length of .

LeetCode Original link https://leetcode.cn/problems/longest-substring-without-repeating-characters/

---

Catalog

Method 1： The sliding window

Method 1 analysis ：

Complexity analysis ：

  Method 2： Optimize sliding windows with hash sets

Method 2 analysis ： 

Complexity analysis ：

---

Method 1： The sliding window

Method 1 analysis ：

  This is the classic The sliding window Type of topic , There is almost a fixed routine ： Determine an interval , Perform some operations on this interval , Then change the position and size of the interval through operation , To solve the problem .

Specific to this problem, the above is ： Set the pointer i Traverse from the beginning , stay i If there was a connection with i The same characters （ Name it same）, Then the length of the non repeating string becomes same The next character of to i The length of . The next cycle only needs to start from same The next character of Start judging , namely same+1 To i （ there i yes i++ After that i ） This interval .

The code is as follows ：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        int MaxLen = 0; // Record the maximum length 
        int same=0; // Used to find in i Before subscript and s[i] The same characters 
        int begin=0; // Record the first position of the non repeating string 
        for (int i = 0; i < size; i++) // Every cycle is recorded with i The length of the longest non repeating string at the end 
        {
            for(same = begin ; same < i ; same++)
            {
                if(s[same]==s[i])
                {
                    begin=same+1;
                    break;
                }
            }
            MaxLen=max(MaxLen,i-begin+1); // Record to i The length of the non repeating string at the end of the subscript 
        }
        return MaxLen;
    }
};

Complexity analysis ：

Time complexity ：, Two layers of circulation .

Spatial complexity ：, Only a constant space is opened .

---

  Method 2： Optimize sliding windows with hash sets

Method 2 analysis ： 

Method 1 In, we use a loop to find whether there are the same elements before , This kind of use Loop search The time complexity of the method is O（N）, It's easy to think of using unordered_set（ Hash set ） Can make “ Find whether there is the same element before ” The time complexity of this matter becomes O（1）, Is a typical use of Space for time How to do it . But the whole Execute the process need Minor modifications , see notes that will do .

The code is as follows ： 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        unordered_set<char> lookup; // Create a hash set 
        int MaxLen = 0; // Record the maximum length 
        int end = 0; // Mark the last position of the non repeating string 
        for (int i = 0; i < size; i++) //i Used to mark the first position of a non repeating string , Every cycle is recorded with i The length of the longest non repeating string at the beginning 
        {
            while (end < size && lookup.count(s[end]) == 0)
            {
                lookup.insert(s[end]); // If there are no repeated characters before , Then add this character to the set , And make end Move backward 1 position 
                end++;
            }
            MaxLen = max(MaxLen, end - i); 
            lookup.erase(s[i]); // Delete s[i], That is to i The length of the longest non repeating string at the beginning has been calculated 
        }
        return MaxLen;
    }
};

Complexity analysis ：

Time complexity ：, Subscript i And subscripts end Traverse the string respectively , The loop is executed 2N Time .

Spatial complexity ：,unordered_set opened O（N） Space .

---

  That's all for sharing , I'm not very talented , There must be mistakes or thoughtlessness , If there are corrections or suggestions , Welcome to leave a message in the comment area , I will reply immediately after seeing it and make appropriate changes to the article after thinking , Thank you for reading ~