Overview of sliding Windows
Sliding Window method, also known as the ruler method, can be used to solve some problems of finding properties of continuous intervals (lengths, etc.) that satisfy certain conditions. Operating on a string or array of a particular size, rather than on the whole string or array, reduces the complexity of the problem. Thus, the nesting depth of the loop is reduced. Problems such as “please find xx of the most x interval (substring, subarray) satisfying XX” can be solved using this method.
- Slide: indicates that the window is moving, that is, the movement is in a certain direction.
- Window: the window size is not fixed, can be continuously expanded until certain conditions are met; You can also keep shrinking until you find the smallest window that meets the criteria; It could be a fixed size.
The basic idea of the algorithm:
A string can also be converted into an array. In fact, in essence, sliding Windows operate on an array. For the operation of an array, we generally use a circular class method, while for the sliding window method, in order to improve efficiency, we use an advanced circular method, that is, two Pointers: the left pointer left and the right pointer right.
The content between the two Pointers: [left…right] constitutes a window. With the continuous movement of the pointer, the position and size of the window will change, but the data in the window is always continuous, and the required results can be obtained by processing these data.
As shown in the figure below, set the size of the sliding window to 3. When the sliding window moves across the array each time, calculate the sum of the elements in the current sliding window and get the result RES:
Combined with the above ideas, we can design the general framework of sliding window, pseudo-code is as follows:
var list = [...]
var left = 0; / / pointer to the left
var right = 0; / / right pointer
var window= [] or {}while(right < list.length) { // The right pointer is smaller than the boundary
window.add(list[right]);// Add elements to the window
right++;// Move right to enlarge the window
// If the window is completed, move left to narrow the window
while (windowMeet the requirements (length <3)) {/ /... For window content processing
sum(window) / / sum res
window.remove(list[left]); // Move the element out of the window
left++; // Zoom out}}Copy the codeThe framework consists of two while loops, with the outer control window expanding and the inner control window shrinking. Here are a few examples.
Leetcode algorithm
3 The oldest string without repeating characters
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.Copy the codeExample 2:
Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the codeExample 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.Copy the codeExample 4:
Input: s = "output: 0Copy the codeFirst of all, we need to make it clear that substrings are generally continuous and subsequences are generally discontinuous, so when we solve for substrings, it’s easy to think of the sliding window solution.
The size of the window is not fixed. Therefore, we need to find a critical condition to determine when it is appropriate to adjust the data inside the window, that is, when the inner while loop is executed.
Since the title requires non-repeating characters, in many cases, Map is used to count whether characters in a string are repeated, that is, the key value is a single character, and the value is the number of occurrences of the character, as follows:
var str = 'abcdea'
var map = {}
for (var i = 0 ; i < str.length ; i++) {
var cur = str[i]
if (map[cur]) {
map[cur] ++
} else {
map[cur] = 1}}map: {"a":2."b":1."c":1."d":1."e":1}
Copy the codeTherefore, if the value of a key in the map is greater than 1, it indicates that the string contains repeated characters. Using this idea, when we use the sliding window, it can be judged as the condition that the window meets the requirements. The overall idea is shown below (picture from Leetcode) :
Where, the Pointers I and J correspond to left and right respectively, and the length of continuous substring after each transformation is calculated by constantly changing the window.
Solution:
var lengthOfLongestSubstring = function(s) {
var map = {} // Count the number of occurrences of each character
var left = 0,right = 0;
var len = s.length
var res = 0
while(right < len) {
var r = s[right]
right++
// The right pointer element enters the window
if (map[r]) {
map[r]++
} else {
map[r] = 1
}
// Duplicate elements found in window
while(map[r] > 1) {
var l = s[left]
// Zoom out
left++
map[l]--
}
// There must be no duplicate values in this window
// Every time the window changes, the maximum length is recorded by pairwise comparison
res = Math.max(res,right-left)
}
return res
};
Copy the codeTime complexity: O(N), where N is the length of the string. Left and right Pointers traverse the entire string once each.
Space complexity: O(N), where N is the number of non-repeating characters in the string, and space is consumed by Map.
239 Maximum sliding window
Given an integer array numS, there is a sliding window of size K that moves from the leftmost of the array to the rightmost 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: nums = [1, 3, 1, 3,5,3,6,7], k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the codeExample 2:
Input: nums = [1], k = 1Copy the codeExample 3:
Input: nums = [1,-1], k = 1Copy the codeExample 4:
Input: nums = [9,11], k = 2 output: [11]Copy the codeExample 5:
Enter: nums = [4, -2], k = 2Output:4]
Copy the codeIn LeetCode, this is a hard problem, but it is easy to provide a solution using our sliding window framework idea above.
First of all, the size of the window in the title is fixed, so we only need to move the window, that is, move the left and right Pointers synchronously, while the window in the inner while loop meets the requirements. It is very simple to directly determine whether the window length meets the requirements. The core code is as follows:
var window = []
while (right < nums.length) {
var r = nums[right]
right++
window.push(r)// The right element enters the window
while (window.length == k) { // The window length is k
max(window) // Calculate the maximum value in the window
window.shift()// Move the left element out of the window
left++ // Window moves to the right}}Copy the codeBasic idea:
- Use the sliding window to traverse the number group.
- The window object is an array to which elements are added each time the pointer moves to the right.
- When the window size fits
k, calculate the maximum value in the window, and then the window as a whole moves to the right. - When the right pointer reaches the boundary, the traversal is complete.
Solution:
var maxSlidingWindow = function(nums, k) {
if (k == 1) return nums
var right = 0,left = 0
var window = []
var res = []
while (right < nums.length) {
var r = nums[right]
right++
window.push(r)
while (window.length == k) {
res.push(Math.max(... window))// use math.max to find the maximum value
window.shift()
left++
}
}
return res
};
Copy the codeBut as the topic of a hard difficulty, the difficulty lies in the time complexity, the above solution, every time we seek maximum data from a window, use Math. Max () method, it is actually very consumption, the performance of the underlying actually to traverse the window, and achieved to the maximum, such increased by a large part of the cycle time complexity.
We can think about, window window only need to get the maximum value, then we can set the window to a monotone decreasing array queue, when the new elements into the window than before hours, abandoned directly, then the maximum or the last maximum value, thus saving time, the introduction of monotone queue.
Monotonic queue basic idea:
Original queue: [1 3-1-3 5 3].
Queues are always maintained to keep them decreasing, so something like this happens:
| operation | The queue status |
|---|---|
| 1 team | [1] |
| 3 in, bigger than 1, 1 out | [3] |
| 1 team | (3, 1] |
| – 3 team | [3, -1, -3] |
| 5 join the queue, larger than -3, delete the previous elements, and then compare and delete | [5] |
| 3 team | [5] |
The code is as follows:
class maxQueue {
constructor(){
this.items = []
}
// Enter the queue
enqueue(ele){
// Delete all previous elements smaller than the new element
while(this.items.length && this.items[this.items.length-1] < ele) {
this.items.pop()
}
this.items.push(ele)
}
// The team goes out first
dequeue(ele){
// Determine if the element needs to be removed
if (this.items.length && this.items[0] == ele) {
this.items.shift()
}
}
// The head of the team is the biggest element
front(){
return this.items[0]}max(){
return this.front()// The head of the team is the biggest element}}Copy the codeAfter introducing the priority queue, transform our overall solution as follows:
Solution:
var maxSlidingWindow = function(nums, k) {
if (k == 1) return nums
var right = 0,left = 0
var window = new maxQueue()
var res = []
while (right < nums.length) {
var r = nums[right]
right++
window.enqueue(r)
while (right-left >= k) {
var l = nums[left]
res.push(window.max())
window.dequeue(l)
left++
}
}
return res
};
Copy the code** Time complexity: **O(N logN) where N is the length of the NUMS array. Left and right Pointers traverse the entire string once each. In the worst case, the elements in the array NUMS are monotonically increasing, so that the priority queue eventually contains all elements and no elements are removed. Since the time to put an element into the priority queue is O(log N), the total time is O(N logN).
** Space complexity: **O(N), where N is the space required by the priority queue.
76 Minimum coverage substring
I give you a string S, a string t. Returns the smallest string in S that covers all characters of t. Return an empty string “” if there is no substring in S that covers all characters of t.
Note:
-
For repeated characters in T, we must look for substrings that have at least the number of characters in t.
-
If such a substring exists in s, we guarantee that it’s the only answer.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC" output: "BANC"Copy the codeExample 2:
Input: s = "a", t = "a" output: "a"Copy the codeExample 3:
Input: s = "a", t = "aa" Output: "" Explanation: both characters 'a' in t should be included in the substring of S, so there is no qualified substring, return empty string.Copy the codeIn the first string, you need to find the permutation of the second string. In the end, you need to find the substring. You can use the sliding window algorithm on the first string s.
First of all, the ultimate goal of the subject is to be found in the s t, but it has not and t are equal, but to find a t the permutation and combination of whether it contains all the elements in the t, because might contain duplicate elements in t, when calculating the permutation and combination, repeating element is not included in the statistics, or use of the Map, first calculate each character, the code is as follows:
var map = {}
var missingType = 0 // Record the number of characters that are not repeated
for (var c of t) {
if (map[c]) {
map[c]++
} else {
map[c] = 1
missingType++
}
}
Copy the codeAfter getting the map, you can use the map to match in S. The code is as follows:
while(right < s.length) {
var r = s[right]
right++
if (map.hasOwnProperty(r)) { // Every time the character entering the window appears in s, the count is -1
map[r]--
}
if (map[r] == 0) {// If the number of characters is 0, the current character is not missing
missingType--
}
while(missingType == 0) { // If all characters match, you can shrink the window
if (right - left < res.length) { / / length
res = s.substring(left,right)
}
var l = s[left]
left++
map[l]++ // Each time a character moves out of the window, the count is increased by 1
if (map[l] > 0) { // If the current character is greater than 0, the character is missing
missingType++
}
}
}
Copy the codeWe slide the window over S, expanding the window by moving the right pointer. When the window contains all the characters t needs, if it can be shrunk, we shrink the window until we get the minimum window, missingType is used to increase the flag bit to record repeated characters. The idea is as follows (image from LeetCode) :
Finally, we need to deal with some boundary conditions, such as s is equal to t, or s contains no T at all. The complete solution is as follows:
Solution:
var minWindow = function(s, t) {
if (t.length > s.length) return ' '
if (t == s) return s
var flag = false
var map = {}
var missingType = 0
var res = s
for (var c of t) {
if(! map[c]) { map[c] =1
missingType++
} else {
map[c]++
}
}
var left = 0,right = 0
while(right < s.length) {
var r = s[right]
right++
if (map.hasOwnProperty(r)) { // Every time the character entering the window appears in s, the count is -1
map[r]--
}
if (map[r] == 0) {// If the number of characters is 0, the current character is not missing
missingType--
}
while(missingType == 0) { // If all characters match, you can shrink the window
flag = true // Find t in s
if (right - left < res.length) { / / length
res = s.substring(left,right)
}
var l = s[left]
left++
map[l]++ // Each time a character moves out of the window, the count is increased by 1
if (map[l] > 0) { // If the current character is greater than 0, the character is missing
missingType++
}
}
}
return! flag ?' ' : res
}
Copy the codeTime complexity: O(N), where N is the length of string S. Left and right Pointers traverse the entire string once each.
Space complexity: O(N), where N is the number of non-repeating characters in the string, and space is consumed by Map.
conclusion
Sliding window questions are frequently asked in interviews. The question itself is not complicated, so it is very important to master the framework.
Other articles:
Front end algorithm: maze problem
Front end algorithm: binary tree traversal
Front end algorithm: palindrome string