Introduction:

Sliding window problem is a high frequency problem in the interview, the problem itself is not complex, but the implementation of the details of thinking is very much, thinking about variable changes, pointer movement and so on, leading to repeated deletion to change the program, thinking, but the program is not written is the biggest obstacle to this kind of problem. This paper will analyze, summarize and classify most sliding window problems in LeetCode, and provide a reference template, which is believed to effectively reduce the uncertainty of algorithm implementation in the interview.


Subject overview

Sliding window problems generally need to use double Pointers to solve, and a special kind of problems need to use a specific data structure, such as SORted_map. The latter has a specific question type, which will be listed later, but for the former, the question shape is very large, generally based on strings and arrays, so we focus on this kind of sliding window problem based on double Pointers.

There are several ways to ask questions:

  • Give two strings, one long and one short, and ask if the shorter exists in the long string. For example:
    • Find the shortest substring that is long. The substring must cover all the short characters
    • All the positions in which the short anagram appears in the long
    • .
  • Given a string or array, ask if the substring or subarray of the string meets certain conditions, for example:
    • The largest string containing less than K distinct characters
    • The oldest string in which all characters occur only once
    • .

In addition, there are some other questions, but the constant is that this kind of question is inseparable from the main array (main array) and the subarray (subarray) relationship, the required time complexity is usuallySpatial complexity is often constant. The reason for the sliding window is that, when traversing, the substring (subarray) between the two Pointers is similar to a window, and the size and scope of this window will change with the movement of the Pointers before and after.


Their thinking

According to the above description, sliding Windows is the focus of this kind of problem. In other words, the movement of Windows is the focus. We want to control the movement of the pointer to control window, before and after such a move is conditional, that is if you want to know under what circumstances, under what circumstances remain the same, I am here about my thoughts, my train of thought is to make sure the right pointer move forward one at a time, each new mobile will be an element into the window, conditions may be changed at this moment, Then according to the current conditions to determine whether the left pointer moves, and how many Spaces to move. I wrote a template here for your reference:

public int slidingWindowTemplate(String[] a, ...) {
    // Determine the validity of input parameters
    if (...) {
        ...
    }
    
    // Apply a hash to record the number of specific elements in the window
    // This is represented as an array. You can also consider other data structures
    int[] hash = new int[...]. ;// Preprocess (save), usually by changing hash.// l represents the left pointer
    // count specifies the current condition
    // result is used to store results
    int l = 0, count = ... , result = ... ;for (int r = 0; r < A.length; ++r) {
        // Update the number of new elements in the hash
        hash[A[r]]--;
        
        // Change the conditional value according to the window change result
        if (hash[A[r]] == ...) {
            count++;
        }
        
        // If the current condition is not met, move the left pointer until the condition is met
        while(count > K || ...) {...if(...). { count--; } hash[A[l]]++; l++; }// Update the result
        results = ...
    }
    
    return results;
}
Copy the code

The “move the left pointer until the condition is satisfied” part of this requires a case-by-case analysis. The other parts do not change much. Let me now look at the specific problem.


Specific topic analysis and code

438. Find All Anagrams in a String

Although this is an easy question, if you are limited inHow about in time complexity? The length of the window is the length of the second string in the input parameter. That is to say, when the right pointer moves to a certain position, the left pointer must move with it, and each move is one space. In the template, count is used to record the elements that meet the conditions in the window. Update the answer until count equals the window length

public List<Integer> findAnagrams(String s, String p) {
    if (s.length() < p.length()) {
        return new ArrayList<Integer>();
    }
    
    char[] sArr = s.toCharArray();
    char[] pArr = p.toCharArray();
    
    int[] hash = new int[26];
    
    for (int i = 0; i < pArr.length; ++i) {
        hash[pArr[i] - 'a'] + +; } List<Integer> results =new ArrayList<>();
    
    int l = 0, count = 0, pLength = p.length();
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r] - 'a']--;
        
        if (hash[sArr[r] - 'a'] > =0) {
            count++;
        }
        
        if (r > pLength - 1) {
            hash[sArr[l] - 'a'] + +;if (hash[sArr[l] - 'a'] > 0) {
                count--;
            }
            
            l++;
        }
        
        if(count == pLength) { results.add(l); }}return results;
}
Copy the code


76. Minimum Window Substring

The relationship between the two strings is also a problem, because the smallest string, which is the minimum length of the window, means that the window size is variable, and the condition for moving the left pointer is to move it whenever the left pointer points to an unwanted character

public String minWindow(String s, String t) {
    if (s.length() < t.length()) {
        return "";
    }
    
    char[] sArr = s.toCharArray();
    char[] tArr = t.toCharArray();
        
    int[] hash = new int[256];
    
    for (int i = 0; i < tArr.length; ++i) {
        hash[tArr[i]]++;
    }
    
    int l = 0, count = tArr.length, max = s.length() + 1;
    String result = "";
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r]]--;
        
        if (hash[sArr[r]] >= 0) {
            count--;
        }
        
        while (l < r && hash[sArr[l]] < 0) {
            hash[sArr[l]]++;
            l++;
        }
        
        if (count == 0 && max > r - l + 1) {
            max = r - l + 1;
            result = s.substring(l, r + 1); }}return result;
}
Copy the code


159. Longest Substring with At Most Two Distinct Characters

The window size changes, but the key is when to update the left pointer. So the count here can be used to keep track of how many different characters there are, and as long as the character that’s currently in the window doesn’t satisfy count, we move the left pointer so that count does. Here result is initialized to 1, because as long as the input string is not empty, the window size cannot be less than 1.

public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    
    char[] sArr = s.toCharArray();
    
    int[] hash = new int[256];
    
    int l = 0, count = 0, result = 1;
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r]]++;
        
        if (hash[sArr[r]] == 1) {
            count++;
        }
        
        while (count > 2) {
            hash[sArr[l]]--;

            if (hash[sArr[l]] == 0) {
                count--;
            }

            l++;
        }
        
        result = Math.max(result, r - l + 1);
    }
    
    return result;
}
Copy the code


340. Longest Substring with At Most K Distinct Characters

Just like we did in the previous problem, we can change 2 to k

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s == null || s.length() == 0 || k == 0) {
        return 0;
    }
    
    char[] sArr = s.toCharArray();
    
    int[] hash = new int[256];
    
    int l = 0, count = 0, result = 1;
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r]]++;
        
        if (hash[sArr[r]] == 1) {
            count++;
        }
        
        while (count > k) {
            hash[sArr[l]]--;

            if (hash[sArr[l]] == 0) {
                count--;
            }

            l++;
        }
        
        result = Math.max(result, r - l + 1);
    }
    
    return result;
}
Copy the code


3. Longest Substring Without Repeating Characters

The input is a single string, requiring that there should be no duplicate elements in the substring. Here, the count does not need to be defined, and the elements in the hash should be determined directly. If so, the left pointer should be moved to duplicate the elements.

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    
    char[] sArr = s.toCharArray();
    int[] hash = new int[256];
    
    int l = 0, result = 1;
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r]]++;
        
        while(hash[sArr[r]] ! =1) {
            hash[sArr[l]]--;
            l++;
        }
        
        result = Math.max(result, r - l + 1);
    }
    
    return result;
}
Copy the code


567. Permutation in String

Very similar to 438, but I don’t need to record the answer, so I’ll just return true.

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }
    
    char[] s1Arr = s1.toCharArray();
    char[] s2Arr = s2.toCharArray();
    
    int[] hash = new int[26];
    
    for (int i = 0; i < s1Arr.length; ++i) {
        hash[s1Arr[i] - 'a'] + +; }int l = 0, count = 0;
    for (int r = 0; r < s2Arr.length; ++r) {
        hash[s2Arr[r] - 'a']--;
        
        if (hash[s2Arr[r] - 'a'] > =0) {
            count++;
        }
        
        if (r >= s1Arr.length) {
            hash[s2Arr[l] - 'a'] + +;if (hash[s2Arr[l] - 'a'] > =1) {
                count--;
            }
            
            l++;
        }
        
        if (count == s1Arr.length) {
            return true; }}return false;
}
Copy the code


992. Subarrays with K Different Integers

Ok, so if you look at the string problem, let’s look at the array problem, and the subarray problem already specifies that you can use a sliding window, and one of the tricks of this problem is that instead of taking a minimum or a maximum, you’re going to have to count, and if you’re just incrementing by 1, For example, if A = [1,2,1,2,3], K = 2, if the right pointer moves to the position where index is 3, if the left pointer moves according to count, the current window is [1,2,1], but how to take into account [2,1]? If [1,2,1,2] is a qualified array, are the results of [1,2,1] related to the results of [1,2,1]? More than the difference between the two array elements, a new came in before the child didn’t consider this element array count, if put the element before eligible child array of new array is in conformity with the conditions, we look at this case all meet the conditions of the window and the corresponding meet the condition of sub array:

,2,1,2,3 [1] / / the window the r/l/meet the conditions of subarray,2,1,2,3 [1] [1, 2] / / the window the r/l/meet the conditions of subarray [1, 2], [2, 1], [1, 2, 1],2,1,2,3 [1] / / Window to meet the conditions of r/l/meet the conditions of subarray [1, 2], [2, 1], [1, 2, 1], [1, 2], [2,1,2], [1,2,1,2],2,1,2,3 [1] / / window does not meet the conditions, Moves the pointer left to meet the conditions of the l r,2,1,2,3 [1] / / the window the r/l/meet the conditions of subarray [1, 2], [2, 1], [1, 2, 1], [1, 2], [2,1,2],,2,1,2 [1], [2, 3]Copy the code

You can see that for a contiguous array, new elements come in, the window increments by 1, and each increment increases by 1. When a new element comes in and breaks the current condition, the increment goes back to 1, so our left pointer move condition means move as long as it doesn’t change the condition, or stop

public int subarraysWithKDistinct(int[] A, int K) {
    if (A == null || A.length < K) {
        return 0;
    }
    
    int[] hash = new int[A.length + 1];
    
    int l = 0, results = 0, count = 0, result = 1;
    for (int r = 0; r < A.length; ++r) {
        hash[A[r]]++;
        
        if (hash[A[r]] == 1) {
            count++;
        }
        
        while (hash[A[l]] > 1 || count > K) {
            if (count > K) {
                result = 1;
                count--;
            } else {
                result++;
            }
            hash[A[l]]--;
            l++;
        }
        
        if(count == K) { results += result; }}return results;
}
Copy the code


424. Longest Repeating Character Replacement

This is easy to accept, but the problem is how to know the maximum number of characters in the current window, because the character to be replaced is the size of the current window minus the maximum number of characters in the window. The easiest way to do this is to go through the hash hash and find the maximum number of characters, but if you think about it if we update this maximum number every time we enter a new element, and only once, we’re keeping the maximum number of characters that we’re currently walking through globally, which is definitely greater than the actual maximum, Max (r-l + 1, result); Max (r-l + 1, result); If maxCount is larger than it should be, the left pointer will not move, but the current result will not be recorded, so the final answer will not be affected

public int characterReplacement(String s, int k) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    
    char[] sArr = s.toCharArray();
    
    int[] hash = new int[26];
    
    int l = 0, maxCount = 0, result = 0;
    for (int r = 0; r < sArr.length; ++r) {
        hash[sArr[r] - 'A'] + +; maxCount = Math.max(maxCount, hash[sArr[r] -'A']);
        
        while (r - l + 1 - maxCount > k) {
            hash[sArr[l] - 'A']--;
            l++;
        }
        
        result = Math.max(r - l + 1, result);
    }
    
    return result;
}
Copy the code


Other questions

239. Sliding Window Maximum

Refer to the algorithms section of Arts I wrote earlier -> Arts Week 3


480. Sliding Window Median

For the problem of value is more special, if is the best under the condition of random sequence is by the heap, using two heap, a big top, a small top, and ensure that the two deposit in pile by the number of not more than 1, so that if the current element number is an even number, the average is the result of two heap top elements, if it is odd, storage elements that pile of pile top element is the result.

public double[] medianSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length < k ) {
        return new double[0];
    }
    
    double[] results = new double[nums.length - k + 1];
    
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    
    for (int i = 0; i < nums.length; ++i) {
        // add current element into queue
        maxHeap.offer(nums[i]);
        minHeap.offer(maxHeap.poll());
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
        
        // record answer
        if (i >= k - 1) {
            results[i - k + 1] = minHeap.size() < maxHeap.size() 
                    ? maxHeap.peek() : ((long)maxHeap.peek() + minHeap.peek()) * 0.5;

            if (maxHeap.contains(nums[i - k + 1])) {
                maxHeap.remove(nums[i - k + 1]);
            } else {
                minHeap.remove(nums[i - k + 1]); }}}return results;
}
Copy the code


conclusion

The thinking complexity of sliding window problem of double-pointer class is not high, but the error point is often in the details. It is necessary to memorize common problem solving templates, especially for questions with many variable names that are easily confused. With this framework, the thinking point is transformed into “under what conditions to move the left pointer”, less irrelevant information, thinking and implementation is not a problem naturally.