LeetCode3_ Longest substring without duplicate characters

Original article , Reprint please indicate the source .

Topic type ： secondary

The title is as follows

Given a string , 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 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"  Is a subsequence , Not substring .
     
 Example  4:
 Input : s = ""
 Output : 0

Tips ：

0 <= s.length <= 5 * 104
s  By the English letters 、 Numbers 、 Symbols and spaces 

solution

 Ideas ：
 The main idea of this problem is ： The sliding window 
	
 What is a sliding window ？

 It's actually a queue , For example, in the example  abcabcbb, Enter this line （ window ） by  abc  Meet the requirements of the topic ,
 When you enter  a, The queue becomes  abca, Not meeting the requirements at this time . therefore , We're going to move this queue ！

 How to move ？

 All we have to do is move the elements on the left side of the queue , Until the subject requirements are met ！

 Keep this line up all the time , Find out the maximum length of the queue , Find out the solution ！

 Time complexity ：O(n)

The code implementation is as follows

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
    
        // String length 
        int nLen = s.length();
        // Character hash set ,  The same characters are not allowed 
        unordered_set<char> chardata;
        // Index started ,  Maximum length 
        int nStart = -1, nMax = 0;

        for(int i = 0; i < nLen; i++)
        {
    
            // The sliding window ,  Every time remove Drop the first character 
            if(i != 0)
            {
    
                //leetcode It must be written in this way :chardata.erase(s[i-1]), use //chardata.erase(chardata.begin()); incorrect .
                chardata.erase(s[i-1]);
                //VC++ In the environment //chardata.erase(chardata.begin()); Yes. 
                //chardata.erase(chardata.begin());
            }

            // Add non repeating characters in turn 
            while(nStart+1 < nLen && chardata.count(s[nStart+1]) == 0)
            {
    
                chardata.insert(s[nStart+1]);
                ++nStart;
            }

            // Calculate the maximum length 
            nMax < chardata.size() ? nMax = chardata.size() : nMax;

            // Check whether the maximum length under the current cycle has been reached 
            if(nMax == nLen-i) break;
        }

        return nMax;
    }
};

leetcode score

thank you , It's not easy to create , Great Xia, please stay … Move your lovely hands , Give me a compliment before you go <(￣︶￣)>