Leetcode daily practice (longest substring without repeated characters)

The title is as follows ：

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

The problem requires finding the longest substring without repeated characters in a given string , We can use violence and exhaustion , Get all substrings in the string , Then judge the length of non repeating substrings one by one , Finally, return the length of the longest substring , such as ：

For such a string , Let's start from scratch , take a Take out ：

Then take out the next character b, Check whether the character is repeated , If not repeated , Continue to put in the new string ：

Next character c So it is with ：

The next character is a, At this point, it is found that there are already characters in the new string a, There was a repetition , So now record the length of the new string , by 3, Then continue the traversal from the second character of the original string ：

Look at the next character c, Still put the new string ：

Until characters are encountered b, There is repetition ：

The length of the current new string is still recorded , And traverse from the third character of the original string ：

And so on , A length table of non repeating character substrings is obtained ：

At this time, just take out the maximum value in the length table , That is, the length of the longest substring without repeated characters in the string .

After knowing the idea of the algorithm , You can write code ：

public static int lengthOfLongestSubstring(String s) {
    
        //  Use List Set to determine whether characters appear repeatedly 
        List<Character> list = new ArrayList<>();
        //  Store the length of all non repeating substrings 
        List<Integer> lenList = new ArrayList<>();
        //  Record substring length 
        int count = 0;
        char[] charArray = s.toCharArray();
        //  Enumerate all substrings 
        for (int i = 0; i < charArray.length; ++i) {
    
            for (int j = i; j < charArray.length; ++j) {
    
                //  Determine whether the characters appear repeatedly 
                if (list.contains(charArray[j])) {
    
                    //  If it appears , Record the length of the current substring 
                    lenList.add(count);
                    //  Set empty ,count return 0
                    list.clear();
                    count = 0;
                    //  End this cycle 
                    break;
                } else {
    
                    //  If not , Then add 
                    list.add(charArray[j]);
                    count++;
                }
            }
        }
        //  Sort the set with no repeated substring length from large to small 
        lenList.sort((o1, o2) -> o2 - o1);
        //  The first element after sorting is the maximum value in the collection 
        return lenList.get(0);
    }

Submit the code , Result error ：

It turns out that we didn't consider entering anything , If there is no input , The length is returned directly 0 that will do , For length is 1 The input of , We have to consider it alone , Because the program just now records the length of the current substring only when there are repeated characters , If the length of the input string is 1, There is no repetition , So we can deal with these two cases separately , Modify the code ：

public static int lengthOfLongestSubstring(String s) {
    
        //  If the string length is 1, Then return directly 1
        if (s.length() == 1) {
    
            return 1;
        }
        //  If there is no input , Then return directly 0
        if (s.length() == 0) {
    
            return 0;
        }
        //  Use List Set to determine whether characters appear repeatedly 
        List<Character> list = new ArrayList<>();
        //  Store the length of all non repeating substrings 
        List<Integer> lenList = new ArrayList<>();
        //  Record substring length 
        int count = 0;
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; ++i) {
    
            for (int j = i; j < charArray.length; ++j) {
    
                //  Determine whether the characters appear repeatedly 
                if (list.contains(charArray[j])) {
    
                    //  If it appears , Record the length of the current substring 
                    lenList.add(count);
                    //  Set empty ,count return 0
                    list.clear();
                    count = 0;
                    //  End this cycle 
                    break;
                } else {
    
                    //  If not , Then add 
                    list.add(charArray[j]);
                    count++;
                }
            }
        }
        //  Sort the set with no repeated substring length from large to small 
        lenList.sort((o1, o2) -> o2 - o1);
        //  The first element after sorting is the maximum value in the collection 
        return lenList.get(0);
    }

The test passed ：

Although violent exhaustion solves the problem, it needs , But the execution efficiency is very low , So , Here is another solution ： The sliding window .

For such a string ：

We set up a sliding window , The substring in this window is the longest substring without repeated characters , Define two pointers to divide the left and right boundaries of the window , And specify that the longest substring length at this time is 1：

Give Way right Move the pointer to the right. , Expand the sliding window range , At this time, the longest substring length is 2：

Keep moving right right The pointer , The longest substring length is 3：

When you move right again right When the pointer , Find the character a Already appears in the sliding window ：

At this point, we need to narrow the sliding window , Make it no longer associated with the current character a repeat , Give Way left Move the pointer to the right. ：

When the sliding window is no longer associated with characters a After repetition , Expand the sliding window ,right Move right , At this time, the longest substring length is still 3：

At this time, the character b Repeat with characters in the window , Continue to narrow the sliding window ：

After no repetition , Expand the sliding window ,right Move the pointer to the right. ：

And so on , Until the end of the traversal .

The code is as follows ：

public static int lengthOfLongestSubstring(String s) {
    
        //  If there is no input , Then return directly 0
        if (s.length() == 0) {
    
            return 0;
        }
        //  Define the left boundary of the sliding window 
        int left = 0;
        //  Define the right boundary of the sliding window 
        int right = 0;
        //  Maximum length of non repeating substring 
        int maxLen = 1;
        //  Simulate sliding window 
        Set<Character> set = new HashSet<>();
        //  Traversal string 
        while(right < s.length()){
    
            //  If the character in the sliding window repeats the current character , Then reduce the sliding window , Until there is no repetition 
            while (set.contains(s.charAt(right))) {
    
                set.remove(s.charAt(left));
                left++;
            }
            //  Calculate the current sliding window length , And with maxLen Compare , Take the maximum value as the new non repeating substring length 
            maxLen = Math.max(maxLen, right - left + 1);
            //  Expand the sliding window 
            set.add(s.charAt(right));
            right++;
        }
        return maxLen;
    }

The test passed ：

The algorithm still has some improvements , such as ：

For such a string , When the sliding window encounters duplicate characters ：

The sliding window is now reduced ,left Keep moving right , Until the character w Delete ：

So is there any way to make left Move directly to the next character of the repeated character ？ We can use HashMap To simulate sliding windows , because HashMap You can store a value , Let's just let it store the index of characters .
So when you encounter duplicate characters w when , Directly from HashMap Take it out of the sliding window w The index of 3, And then just let left The pointer jumps to the next index 4 The position of .

The code is as follows ：

public static int lengthOfLongestSubstring(String s) {
    
        //  If there is no input , Then return directly 0
        if (s.length() == 0) {
    
            return 0;
        }
        //  Define the left boundary of the sliding window 
        int left = 0;
        //  Define the right boundary of the sliding window 
        int right = 0;
        //  Maximum length of non repeating substring 
        int maxLen = 1;
        //  Simulate sliding window 
        Map<Character, Integer> map = new HashMap<>();
        //  Traversal string 
        while (right < s.length()) {
    
            //  If the character in the sliding window repeats the current character , Then reduce the sliding window 
            int index = map.getOrDefault(s.charAt(right), -1);
            //  Directly to left The pointer jumps to the next character of the repeated character in the sliding window 
            left = Math.max(left, index + 1);
            //  Calculate the current sliding window length , And with maxLen Compare , Take the maximum value as the new non repeating substring length 
            maxLen = Math.max(maxLen, right - left + 1);
            //  Expand the sliding window 
            map.put(s.charAt(right), right);
            right++;
        }
        return maxLen;
    }