Sliding window algorithm

Principle

The idea of the sliding window algorithm is this:

1. We use the left and right pointer trick in the double pointer in string S, initialize left = right = 0, and call the index closed interval [left, right] a “window”.

2. We first keep increasing the right pointer to expand the window [left, right] until the string in the window meets the requirements (including all the characters in T).

3. At this point, we stop adding right, and instead keep increasing the left pointer to shrink the window [left, right] until the string in the window no longer meets the requirements (does not contain all the characters in T). At the same time, every time we increase left, we have to update the result one round.

4. Repeat steps 2 and 3 until the end of string S is reached to the right.

This idea is actually not difficult. ** The second step is equivalent to finding a “feasible solution”, and then the third step is to optimize this “feasible solution” and finally find the optimal solution. ** The left and right pointers take turns to advance, the window size increases or decreases, and the window keeps sliding to the right.

Example

Link to the topic: https://leetcode-cn.com/problems/minimum-window-substring/

Pseudocode

string s, t;
//Find the "minimum covering substring" of t in s
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    //Move the left zoom-out window if it meets the requirements
    While (window meets requirements) {
        //update res if the substring of this window is shorter
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

Concrete realization

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let start = 0, minLength = s.length + 10;
    let left = 0, right = 0;
    let needs = {}, where = {};
    t.split('').forEach((t1) => {
        needs[t1] = needs[t1] ? needs[t1] + 1 : 1;
    })
    let match = 0, needMatch = Object.keys(needs).length;
    while (right < s.length) {
        const s0 = s[right];
        if (!!needs[s0]) {
            where[s0] = where[s0] ? where[s0] + 1 : 1;
            if (where[s0]  needs[s0]) {
                match++;
            }
        }
        right++;
        while(match = needMatch) {
            if (right - left < minLength) {
                start = left;
                minLength = right - left;
            }
            const s1 = s[left];
            if (!!needs[s1]) {
                where[s1]--;
                if (where[s1] < needs[s1]) {
                    match--;
                }
            }
            left++;
        }
    }
    return minLength = s.length + 10 ? '' : s.substr(start, minLength);
};

Maximum value that does not meet the conditions (Updated on 2021/02/19)

The sliding window algorithm above obtains the shortest length that meets the condition.

But sometimes we find the maximum length that does not meet the condition.

For example, today’s leetcode daily question

https://leetcode-cn.com/problems/max-consecutive-ones-iii/

** The meaning of the question is converted. Convert “You can turn at most K zeros into ones, and find the length of the longest subarray containing only ones” to “Find the longest subarray that allows at most K zeros” **

So in this problem, the condition is: ** subarray contains K or more 0 **.

In this case, our problem-solving template has changed

string s, t;
//Find the "minimum covering substring" of t in s
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    //Move the left zoom-out window if it meets the requirements
    While (window meets requirements) {
        window.remove(s[left]);
        left++;
    }
    //update res if the substring of this window is longer
    res = maxLen(res, window);
}
return res;

Careful observation can be found, in fact, the template does not change much, the most important change is the result of the place changed, from the inner loop to the outer loop.

Why is there such a change?

To understand this we need to really understand what the inner and outer cycles are doing?

• The outer loop is constantly expanding the length of the subarray until the condition is met. ** In other words, the outer loop will iterate over all cases that do not meet the condition. **

• The inner loop keeps shortening the length of the subarray until the condition is not met. ** In other words, the inner loop will iterate over all cases that meet the condition. **

Understood this, let’s solve this problem again, it’s not difficult, just go to the code

var longestOnes = function(A, K) {
  let zeroCount = 0;
  let result = 0;
  let left = right = 0;
  while(right < A.length) {
    if (A[right] ! 1) {
      zeroCount++;
    }
    right++;
    while(zeroCount > K) {
      if (A[left] = 0) {
        zeroCount--;
      }
      left++;
    }
    result = Math.max(result, right - left);
  }
  return result;
};

Seeing here, some people may ask, you only said the shortest that meets the conditions and the longest that does not meet the conditions, so what about the longest that meets the conditions and the shortest that does not meet the conditions?

Regarding this issue, everyone can think about whether the last two are meaningful. The longest that meets the condition can directly judge whether the entire array meets the condition, because the longest that meets the condition can only be the entire array, and the entire array does not meet the condition, and the sub-array is even more impossible. The shortest that does not meet the condition is just to traverse one by one, and use each item in the array to judge whether it meets the condition.

In both cases, there is no need for sliding windows at all.