LeetCode 3. Longest substring without repeated characters & sliding window

Subject requirements

Link to the original title ：3. Longest substring without repeating characters

The questions are as follows ：

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

Examples are as follows ：

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

solution ： The sliding window

Ideas

From the beginning, the string s Traversal , The character traversed each time is used as the starting character of the substring , Then find the longest non repeated substring starting with the current character , One traverse can solve the problem .

You can use one Set Set to maintain the longest non repeated substring stored in each traversal to optimize the ordinary traversal . Suppose the existing string abcda, Then the longest non repeated longest string traversed for the first time is abcd, The corresponding second traversal role bcda, among bcd Part is that it is unnecessary to repeat the comparison in the second traversal , So you can use a collection to store , Remove each iteration Set Set first , The rest of the string must be non repeating , Continue to compare the set after the original string , Space for time .

In the process of problem solving, a pointer always points to the starting position of the new child string , The other pointer always looks for and points to the end of the current longest non repeating substring , Two pointers dynamically form an indefinite length substring , Hence the name sliding window , The essence is a kind of double pointer .

complete AC Code

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        Set<Character> set = new HashSet<Character>();
        int max = 0;
        int right = -1;
        for(int i = 0; i < s.length(); i++){
    
            if(i != 0)set.remove(s.charAt(i - 1));
            while(right + 1 < s.length() && !set.contains(s.charAt(right + 1)))set.add(s.charAt(right++ + 1));
            max = Math.max(max, set.size());
        }
        return max;
    }
}

Complexity analysis

Time complexity ：O(N),n String length , In fact, both pointers need to traverse the string once. The time complexity O(2N), Therefore, the total time complexity O(N).
Spatial complexity ：O(S),S Indicates the total number of characters that may be contained in the string .