Guidelines

There are three parts to every sliding window problem:

• Operation for calculating the property of the window (sum, count of characters)
• Operation to make an invalid window valid again (move the start a bit to the right)
• Recording the best so far result of the property (shortest/longest window)

Template to use:

• Fixed length window Permutation in String

Java

for(int i = l1; i < l2; ++i){
    freqMap[s2.charAt(i) - 'a']--;
    freqMap[s2.charAt(i-l1) - 'a']++;
    if(found(freqMap)) return true;
}

JavaScript

for (let i = l1; i < l2; ++i) {
  freqMap[s2.charCodeAt(i) - "a".charCodeAt()]--;
  freqMap[s2.charCodeAt(i - l1) - "a".charCodeAt()]++;
  if (found(freqMap)) return true;
}

Python

for i in range(l1, l2):
    freqMap[ord(s2[i]) - ord('a')] -= 1
    freqMap[ord(s2[i - l1]) - ord('a')] += 1
    if found(freqMap):
        return True

C++

for (int i = l1; i < l2; ++i) {
    freqMap[s2[i] - 'a']--;
    freqMap[s2[i - l1] - 'a']++;
    if (found(freqMap))
        return true;
}

• Shortest window Minimum Size Subarray Sum - trying to make it invalid

Java

// useful for counting letters of interest
for(char c: t.toCharArray()) freqMap[c]++;
int start = 0, end = 0, cnt = l2;
while(end < l1){
    if(freqMap[s.charAt(end++)]-- > 0) --cnt;
    while(cnt == 0){
        // record the better window if possible
        if(freqMap[s.charAt(start++)]++ == 0) ++cnt;
    }
}

JavaScript

for (let c of t) freqMap[c]++;
let start = 0,
  end = 0,
  cnt = l2;
while (end < l1) {
  if (freqMap[s.charAt(end++)]-- > 0) --cnt;
  while (cnt === 0) {
    // record the better window if possible
    if (freqMap[s.charAt(start++)]++ === 0) ++cnt;
  }
}

Python

for c in t:
    freqMap[c] += 1
start = 0
end = 0
cnt = l2
while end < l1:
    if freqMap[s[end]] > 0:
        freqMap[s[end]] -= 1
        cnt -= 1
    end += 1
    while cnt == 0:
        # record the better window if possible
        if freqMap[s[start]] == 0:
            freqMap[s[start]] += 1
            cnt += 1
        start += 1

C++

for (char c : t) freqMap[c]++;
int start = 0, end = 0, cnt = l2;
while (end < l1) {
    if (freqMap[s[end++]]-- > 0) --cnt;
    while (cnt == 0) {
        // record the better window if possible
        if (freqMap[s[start++]]++ == 0) ++cnt;
    }
}

Java

while(j < nums.length){
    windowSum += nums[j++]; // go to the right (move end to the right)

    while(windowSum >= target){ // try shortening the window by moving the start of it until it become invalid
        minLength = Math.min(minLength, j - i);
        windowSum -= nums[i++];
    }
}

JavaScript

while (j < nums.length) {
  windowSum += nums[j++]; // go to the right (move end to the right)

  while (windowSum >= target) {
    // try shortening the window by moving the start of it until it becomes invalid
    minLength = Math.min(minLength, j - i);
    windowSum -= nums[i++];
  }
}

Python

while j < len(nums):
    windowSum += nums[j] # go to the right (move end to the right)
    j += 1

    while windowSum >= target: # try shortening the window by moving the start of it until it becomes invalid
        minLength = min(minLength, j - i)
        windowSum -= nums[i]
        i += 1

C++

while (j < nums.size()) {
    windowSum += nums[j++]; // go to the right (move end to the right)

    while (windowSum >= target) { // try shortening the window by moving the start of it until it becomes invalid
        minLength = min(minLength, j - i);
        windowSum -= nums[i++];
    }
}

• Longest window Fruit Into Baskets - fixing it once it becomes invalid

Java

while(j < fruits.length){
    map.put(fruits[j], j);

    while(map.size() > 2){ // invalid window, move the start further in array (shrink the window)
        int minIndex = map.values().stream().min(Integer::compare).get(); // find the right index to remove the character from
        map.remove(fruits[minIndex]);
        i = minIndex + 1;
    }

    maxFruits = Math.max(maxFruits, j - i + 1); //record the result
    ++j; // keep going as far to right as possible (expanding the window)
}

JavaScript

while (j < fruits.length) {
  map.set(fruits[j], j);

  while (map.size > 2) {
    // invalid window, move the start further in array (shrink the window)
    let minIndex = Math.min(...map.values());
    map.delete(fruits[minIndex]);
    i = minIndex + 1;
  }

  maxFruits = Math.max(maxFruits, j - i + 1); // record the result
  j++; // keep going as far to the right as possible (expanding the window)
}

Python

while j < len(fruits):
    map[fruits[j]] = j

    while len(map) > 2:
        # invalid window, move the start further in array (shrink the window)
        min_index = min(map.values())
        del map[fruits[min_index]]
        i = min_index + 1

    max_fruits = max(max_fruits, j - i + 1) # record the result
    j += 1 # keep going as far to the right as possible (expanding the window)

C++

while (j < fruits.length) {
    map[fruits[j]] = j;

    while (map.size() > 2) {
        // invalid window, move the start further in array (shrink the window)
        int minIndex = std::min_element(map.begin(), map.end(), [](const auto& a, const auto& b) {
            return a.second < b.second;
        })->first;
        map.erase(fruits[minIndex]);
        i = minIndex + 1;
    }

    maxFruits = std::max(maxFruits, j - i + 1); // record the result
    ++j; // keep going as far to the right as possible (expanding the window)
}

Useful mapping for other types of problems containing a larger set of different characters:

• int[26] for Letters 'a' - 'z' or 'A' - 'Z'
• int[128] for ASCII
• int[256] for Extended ASCII

Calculation over all windows of size k Sliding Window Maximum