“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Due to the epidemic, I began to work remotely from home today. Although it seems that remote work does not need to go out, it is still very inconvenient

  • Eating is a big problem. I used to eat in the canteen of the company, but now I have to cook by myself or take away food
  • Working hours become longer, I have to catch the shuttle bus at ten o ‘clock in the company, and I have no concept of time at home. At the same time, I feel that there are more tasks. Everyone is working overtime, and the internal volume is more serious

Alas, it’s hard to get around to it

Brush and can’t, can’t remember, remember the new question type or not, good to brush the question?

The title

Given a string s, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3. Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1. Example 3:

Input: s = “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wKE”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring. Example 4:

Input: s = “output: 0

Train of thought

This problem is of medium difficulty, I think it is very difficult, if you have not been exposed to it, I guess it is difficult to do it under low algorithm complexity,

The sliding window algorithm is mainly investigated

It sounds cool to have a sliding window, but it’s like a double pointer,

Within the two Pointers are the elements that meet the criteria

If an element does not meet the criteria, the two Pointers move to the right, eliminating the leftmost element

For example, ABC is a window, and when a is encountered, the window becomes BCA

The code is implemented as follows, and the algorithm complexity is O(n2)

public static int lengthOfLongestSubstring2(String s) {
    int result = 0;
    if (s.length() == 0) {
        return result;
    }
    int len = 0;
    int start = 0;
    for (int end = 0; end < s.length(); end++) {
        char cur = s.charAt(end);
        // Check if the previous loop contains the current character
        for (int i = 0; i < end; i++) {
            // If yes, skip the first occurrence of the position and calculate from the subsequent position
            if (s.charAt(i) == cur) {
                start = i + 1;
                len = end - start;
                break;
            }
        }
        result = Math.max(result, ++len);
    }
    return result;
}
Copy the code

To optimize the

The scheme implemented above iterates through the previous data each time to determine if the current character is present

This is certainly not efficient, so consider optimizing through hash tables

public static int lengthOfLongestSubstring(String s) {
    int result = 0;
    if (s.length() == 0) {
        return result;
    }
    // Use map to store the position of the element if the next character appears in the map
    // Prove that the window needs to move to the left. The window left pointer is the next repeating element in the map
    Map<Character, Integer> char2index = new HashMap<>();
    // Start,end to form a sliding window
    for (int start = 0, end = 0; end < s.length(); end++) {
        char element = s.charAt(end);
        if (char2index.containsKey(element)) {
            //char2index.get() +1
            start = Math.max(char2index.get(element) + 1, start);
        }
        result = Math.max(result, end - start + 1);
        char2index.put(element, end);
    }
    return result;
}
Copy the code

summary

The topics related to sliding window are very regular to follow, and I will try to spare some time tomorrow to make a summary and induction of the topics related to sliding window, and sort out the relevant topics again.