preface

The so-called window is a continuous closed set, which is generally represented by left and right pointers, but it will also change according to the meaning of the question, such as the following question

187. Repetitive DNA sequences

All DNA consists of A series of nucleotides abbreviated as' A ',' C ',' G 'and'T', such as "ACGAATTCCG". When studying DNA, identifying repetitive sequences in DNA can sometimes be very helpful.

Write a function to find all target substrings. The length of the target substring is 10 and appears more than once in the DNA string s.

In short, find a substring with length of 10 and multiple occurrences in the string

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<>();
        int n = s.length();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= n; i++) {
            String cur = s.substring(i, i + 10);
            int cnt = map.getOrDefault(cur, 0);
            if (cnt == 1) ans.add(cur);
            map.put(cur, cnt + 1);
        }
        return ans;
    }
}

The window here is a fixed size of 10, which is very simple. Therefore, the core and difficulty of sliding window is sliding, which is to grasp the opportunity to expand and shrink the window. Today we will discuss the solution of sliding window

First, let's look at the routine. We need left and right pointers to save the boundary of the window

// Select a memory set
HashMap<Integer, Integer>map
while(right < size){
  //enlarge a window
  while(){
    right ++;
  }
  //Title Requirements
	doSth......
  //contract the window
  left = right;
}

The above architecture is relatively simple, because the more complex the template, the more difficult it is to remember, and the worse the portability,

These three lines of notes are our three board axe. Next, let's look at some topics

The key thing we should pay attention to is the general situation of expanding the window and the special situation of narrowing the window, that is, the grasp of these two opportunities. Next, we will elaborate through four questions

Normal sliding window

3. Longest substring without repeated characters

This question can be said to be one of the sliding window questions with the highest interview frequency. If you don't stick the question, I think you also know what the question is. Since it is said that there are no repeated characters, as long as there are no repeated characters, we can expand the window. As long as there is a repetition, it is the time to narrow it

We can use map storage and apply the framework. When there is no repetition, we keep put ting, right + +. When there is repetition, we jump out of the loop and update left

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left =  0;
        int right = 0;
        int size = s.length();
        char [] chars = s.toCharArray();
        HashMap<Character, Integer>map = new HashMap<>();
        int maxNumber = 0;
        while(right < size){
            // enlarge a window
            while(right < size){
                if(!map.containsKey(chars[right])){
                    map.put(chars[right], right);
                    right++;
                }else break;
            }
            //Narrow the window. Right has been repeated. As an open interval, take right - left
            maxNumber = Math.max(maxNumber, right - left);
            map.remove(chars[left++]);
        }
        return maxNumber;
    }
}

In the above question, the function of map is memorization. Map is very useful in many questions. The core is that it has the function of memorization. Therefore, map can be used for all keywords such as [repetition] and [counting]. This question is a typical sliding window + map

Next, this is the problem of sword finger offer. It's the same as a hair, but the solution can be changed, that is, exchange the expanded and reduced positions, or change the data structure to set, and set can also undertake some [repetition] functions

Sword finger Offer 48 The longest substring without duplicate characters

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int resMax = 0;
        HashSet<Character>hashSet =  new HashSet<>();
        int l = 0;
        for(int r = 0; r < s.length(); r++){
            char c = s.charAt(r);
          	// contract the window
            while(hashSet.contains(c)){
                hashSet.remove(s.charAt(l++));
            }
            // enlarge a window 
            hashSet.add(c);
          	// Title Requirements
            resMax = Math.max(resMax, hashSet.size());
        }
        return resMax;
    }
}

This is what I emphasize. The important thing is sliding, which is to seize the opportunity to expand and shrink. map, set and the upcoming arrays, list s, sorting, etc. are auxiliary data structures required for correct sliding

Therefore, when there is a sliding window problem, we need to think about two things: one is the time to expand and shrink the window, and the other is to first, what data structure do we need to record the traversed data

Look at this one again

1838. Frequency of the highest frequency element

The frequency of an element is the number of times that element appears in an array.

Give you an integer array nums and an integer k. In the next operation, you can select a subscript of num and increase the value of the element corresponding to the subscript by 1.

After performing up to k operations, returns the maximum possible frequency of the highest frequency element in the array.

Example 1:

Input: num = [1,2,4], k = 5
Output: 3
Explanation: perform three incremental operations on the first element and two incremental operations on the second element. At this time, Num = [4,4,4].
4 is the highest frequency element in the array, and the frequency is 3.

This question is simply a story about how to allocate k yuan to make everyone rich

The sliding window is a box. Everything can be loaded into it. We can add sorting to the array,

Why sort? The difficulty of this problem is how to understand the situation of expanding the window. In fact, as long as k operations can ensure that all numbers are increased to the maximum value within the sliding window range (that is, the rightmost value after sorting), the window can be continuously expanded until it cannot be guaranteed. The calculation formula is

total += (nums[r] - nums[r - 1]) * (r - l);

That is, every time a new value is added to the window, it will consume (Num [R] - num [R - 1]) * (R - L) operations. Because the new value must be larger than the original value, all the numbers of the original window must be increased by the larger part

You may ask why all the original numbers are increased uniformly (Num [R] - num [R - 1]). Are the original numbers the same??

Yes, very simple. This is similar to dp. From the first smallest sliding window, we ensure that all numbers in the sliding window must be equal

The next step is to narrow the window and subtract (Num [R] - num [l])

Sorting + sliding window

class Solution {
    public int maxFrequency(int[] nums, int k) {
        // sort
        Arrays.sort(nums);
        int res = 1;
        int total = 0;
        int l = 0;
        for(int r = 1; r < nums.length; r++){
            // Expand the window to record the required resources
            total += (nums[r] - nums[r - 1]) * (r - l);
            // Narrow the window if it's not enough
            while(total > k){
                total -= nums[r] - nums[l];
                l ++;
            }
            // Title Requirements: take the maximum value
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

Advanced sliding window

The next one will be more difficult. It's also very classic

239. Maximum value of sliding window

Give you an integer array nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

Example 1:

Input: num = [1,3, - 1, - 3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Maximum position of sliding window

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

This problem is difficult. In essence, it is still difficult to grasp the opportunity to narrow the window

Before shrinking the window, the left pointer was moved to the right. In this problem, the task of shrinking the window should be left to the window itself, because we are looking for the maximum value in the window, and other values don't care, so we only need to put the maximum value on one side of the window, and other values can be removed

Therefore, in addition to the conventional reduction window, there is another reduction, that is, when the newly added value exceeds the maximum value of the original window, all the values of the original window have no effect and can be removed

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 2) return nums;
        // Bidirectional queue saves the array position of the maximum value of the current window, and ensures that the number of array positions in the queue is sorted from large to small
        LinkedList<Integer> list = new LinkedList();
        int[] result = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            // The extra zoom window is guaranteed to pop up from large to small if the front number is small
            while(!list.isEmpty() && nums[list.peekLast()] <= nums[i]){
                list.pollLast();
            }
            // Expand the window to add the array subscript corresponding to the current value
            list.addLast(i);
            // Shrink the window until the window length is k. the next move is to delete the expired value
            if(list.peek() <= i - k){
                list.poll();   
            } 
            // Title Requirements: save the maximum value in the current window when the window length is k
            if(i - k + 1 >= 0){
                result[i - k + 1] = nums[list.peek()];
            }
        }
        return result;
    }
}

The next topic is a little more difficult, but I believe you already know. Even if you haven't done it, you know that after we have simply written the framework, we should discuss the opportunity to expand and narrow the window

76. Minimum coverage substring

Give you a string s and a string t. Returns the smallest substring of s covering t all characters. If there is no substring covering t all characters in s, the empty string "" is returned.

Simply put, find the shortest substring in s that can contain all the letters in t

There are two cases to expand the window. One is that the characters in s are unnecessary and redundant. Then expand normally

The second is that characters are needed, but they do not cover t, so they need to be expanded

For the second, in addition to expanding the window, obviously, we also need to record how many characters of t are currently covered, so we need a have array and the corresponding need array

For narrowing the window, there is only one case, that is, it covers T. you can intuitively know that as long as the frequency of all characters in the have array exceeds that of the need array, but this is a little troublesome. We can define an additional character satisfied by the count record, when count == t.length()

When the timing of downsizing is mastered, the next step is how to downsize. In addition to left + +, the count and have arrays should be updated synchronously. In order to finally output the substring, a start tag index is required to record the position of the minimum coverage substring, and left continues to slide forward

class Solution {
    public String minWindow(String s, String t) {
        // exceptional case
        if(s == null || s == "" || t == null || t == "" || s.length() < t.length())return "";
        // Define array
        int [] have = new int[128];
        int [] need = new int[128];
        for(char c : t.toCharArray()){
            need[c]++;
        }
        // define window
        int right = 0, left = 0;
        int min = s.length() + 1;
        int count = 0; // Total number of characters matched
        int start = 0; // The starting position of the smallest string
        char [] chars = s.toCharArray();
        while(right < s.length()){
            char c = chars[right];
            // There are two cases of expanding the window
            if(need[c] == 0){      // Unnecessary situation
                right++;
                continue;
            }
            if(have[c] < need[c]){   // What we have is not enough
                count++;
            }
            have[c]++;
            right++; // Right is added at the end to indicate left closing and right opening
            // contract the window
            while(count == t.length()){
                //Update minimum window
                if(right - left < min){
                    min = right - left;
                    start = left;
                }
                char l = chars[left];
                // Update left
                if(need[l] == 0){
                    left++;
                    continue;
                }
                if(have[l] == need[l])count--;
                have[l]--;
                left ++;
            }
        }
      return min == s.length() + 1? "":s.substring(start, start + min);
    }
}

summary

The above questions are classic questions that I find out very often according to the interview frequency. To sum up, for the sliding window, the core lies in the timing of sliding, that is, the timing of expanding and narrowing the window. Generally, for the array, we can sort the array in advance as needed

The window is updated with left and right pointers. In case of memory operations, the traversed data can be placed in map, set or list or even multiple sets as needed. The framework is as follows

// Select a memory set
HashMap<Integer, Integer>map
while(right < size){
  //enlarge a window
  while(){
    right ++;
  }
  //Title Requirements
	doSth......
  //contract the window
  left = right;
}

Next, let's give you two classic thinking questions, one easy and one medium. Interested partners can do it and test themselves

219. Duplicate Element II exists

Give you an integer array nums and an integer k, judge whether there are two different indexes I and j in the array, and satisfy nums[i] == nums[j] and ABS (I - J) < = K. If it exists, return true; Otherwise, false is returned.

Example 1:

Input: num = [1,2,3,1], k = 3
Output: true

220. Duplicate element III is present

Give you an integer array nums and two integers k and t. Please judge whether there are two different subscripts I and j, so that ABS (Num [i] - num [J]) < = t and ABS (I - J) < = k.

Returns true if it exists and false if it does not exist.