[jz48 longest substring without repeated characters]

describe

Please find the longest substring in the string that does not contain duplicate characters , Calculate the length of the longest substring .

Data range : s.length ≤ 40000

Example 1

 Input ： "abcabcbb"

 Return value ：3

 explain ： Because the longest substring without repeating characters is "abc", So its length is  3.    

Example 2

 Input ： "bbbbb"

 Return value ：1

 explain ： Because the longest substring without repeating characters is "b", So its length is  1.    

Example 3

 Input ： "pwwkew"

 Return value ： 3

 explain ： Because the longest substring without repeating characters is  "wke", So its length is  3.
 Please note that , Your answer must be the length of the substring ,"pwke"  Is a subsequence , Not substring .  	

Method ： The sliding window

Ideas and algorithms

Let's use an example to consider how to pass the problem in a better time complexity .

Let's take the string in example one abcabcbb For example , find Starting with each character , The longest substring that does not contain duplicate characters , Then the longest string is the answer . For the string in example 1 , We list these results , The brackets indicate the selected character and the longest string ：

• With (a)bcabcbb The longest string to start with is (abc)abcbb;
• With a(b)cabcbb The longest string to start with is a(bca)bcbb;
• With ab(c )abcbb The longest string to start with is ab(cab)cbb;
• With abc(a)bcbb The longest string to start with is abc(abc)bb;
• With abca(b)cbb The longest string to start with is abca(bc)bb;
• With abcab(c )bb The longest string to start with is abcab(cb)b;
• With abcabc(b)b The longest string to start with is abcabc(b)b;
• With abcabcb(b) The longest string to start with is abcabcb(b).

What was found ？ If we enumerate the starting positions of substrings incrementally in turn , Then the end position of the substring is also increasing ！ The reason for this is , Let's say we choose the second... In the string k Two characters as the starting position , And the end position of the longest substring without repeated characters is r[k]. So when we choose the second k+1 When you start with two characters , First of all, from the k+1 To r[k] The character of is obviously not repeated , And because of the lack of the original k Characters , We can try to keep growing r[k] , Until a duplicate character appears on the right .

thus , We can use 「 The sliding window 」 To solve this problem ：

• We use two pointers to represent a substring in a string （ Or window ） The left and right borders of , The left pointer represents the 「 Enumerates the starting position of the substring 」, And the right pointer is the r[k];
• In every step of the operation , We'll move the left pointer one space to the right , Express Let's start by enumerating the next character as the starting position , And then we can keep moving the right pointer to the right , But we need to ensure that there are no duplicate characters in the substring corresponding to these two pointers . At the end of the move , This substring corresponds to Starting with the left pointer , The longest substring that does not contain duplicate characters . We record the length of this substring ;
• At the end of the enumeration , The length of the longest substring we found is the answer .

Judge the repeated characters

In the above process , We also need to use a data structure to judge Whether there are duplicate characters , The common data structure is hash set （ namely C++ Medium std::unordered_set,Java Medium HashSet,Python Medium set, JavaScript Medium Set）. When the left pointer moves to the right , We remove a character from the hash set , When the right pointer moves to the right , We add a character to the hash set .

thus , We solved the problem perfectly .

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
    
        //  Hash set , Record whether each character appears 
        unordered_set<char> occ;
        int n = s.size();
        //  Right pointer , The initial value is  -1, It's like we're on the left side of the left bound of the string , It's not moving yet 
        int rk = -1, ans = 0;
        //  Enumerate the position of the left pointer , The initial value is implicitly expressed as  -1
        for (int i = 0; i < n; ++i) {
    
            if (i != 0) {
    
                //  The left pointer moves one space to the right , Remove a character 
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
    
                //  Keep moving the right pointer 
                occ.insert(s[rk + 1]);
                ++rk;
            }
            //  The first  i  To  rk  A character is a very long non repeating character substring 
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

The elapsed time ：10ms
exceed 16.93% use C++ Submitted code
Take up memory ：656KB
exceed 30.60% use C++ Submitted code
Complexity analysis
Time complexity ：O(N)O(N), among NN Is the length of the string . The left pointer and the right pointer traverse the entire string once, respectively .
Spatial complexity ：O(∣Σ∣), among Σ Represents the character set （ The characters that can appear in a string ）,∣Σ∣ Represents the size of the character set . The character set is not specified in this question , So you can default to all ASCII Code in [0,128) In the character , namely ∣Σ∣=128. We need to use hash sets to store the characters that appear , The characters are at most ∣Σ∣ individual , So the space complexity is zero O(∣Σ∣).

Refer to ：LeetCode-Solution