A, the title

Given a string, find the length of the smallest string that does not contain repeating characters. 【 Force link 】

Second, the sample

Example 1:

Input:"abcabcbb"Explanation: Because the oldest string without repeating characters is"abc"So its length is 3.Copy the code

Example 2:

Input:"bbbbb"Explanation: Because the oldest string without repeating characters is"b"So its length is 1.Copy the code

Example 3:

Input:"pwwkew"Explanation: Because the oldest string without repeating characters is"wke"So its length is 3. Note: Your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Three, the analysis

This may seem like an easy question, but the official level of difficulty has been defined as medium to medium, indicating that there are still some unexpected points that can be ignored.

The first thing you think about this problem is window-sliding. Return the largest window, so we can turn the string into an array first, so that we can move the window, once we have the track to move, we need a window. Defines a window lvalue and an rvalue of the window. The window rvalue can be the subscript of the traversed track. We also need a value for the maximum length returned, as well as the length of the current window, to compare the resulting window length after each move. There seems to be no problem, but there’s actually a trace missing. Plus a set of trajectories that we’ve already traveled. Then you can move the window.

Four, implementation,


public class LengthOfLongestSubstring {
    
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int max = 0;
        int tempLength = 0;
        Map<Character, Integer> lujing = new HashMap<>();
        for (int right = 0; right < chars.length; right++) {
            char c = chars[right];
            Integer index = lujing.get(c);
            lujing.put(c, right);
            // If it does not exist, or if it does not exist within the current range, add a temporary length
            if (index == null || index < left) {
                tempLength = right - left + 1;
                continue;
            }
            // If the temporary length is greater than the current maximum, update the maximum
            if (tempLength > max) {
                max = tempLength;
            }

            // Temporary length changes
            tempLength = right - index;
            // Move forward one bit
            left = index + 1;
        }
        if (tempLength > max) {
            return tempLength;
        }
        returnmax; }}Copy the code

Let’s first turn a string into an array. So we can slide. Lujing is a variable that records the paths taken to see if there are any duplicates. Iterate through the array to see if the current path is in the current window. If not, the window can be added. If it does, it’s compared to the largest path, if it’s bigger than the largest path. Update this value to the maximum value. The temporary length is then recalculated. And move the value of the left window forward one bit.

Five, thank you

Thank you to every reader who took your precious time to read my not at all gorgeous article.