Lesson 7.4 · Sliding Window

Windows with Counts and the "At Most K" Trick

Keep a count map of what's inside the window, track how many requirements are met, and turn "exactly K" into "at most K" minus "at most K − 1".

15 min

Think of it like this

A cashier's tray with a slot per coin type. As coins enter and leave the window you adjust each slot, and you keep one extra note: how many coin types currently meet the order's requirement, so you never need to check every slot.

1.Count maps and a "satisfied" counter

For problems like "smallest window containing all letters of t", keep need[c] (from t) and have[c] (in the window). Maintain formed, the number of letters whose have has reached need. Update it only when a count crosses the requirement, so validity checks are O(1).

2.Exactly K = at most K − at most (K − 1)

Counting subarrays with exactly K distinct values is awkward for a window: adding an element can keep the count at K, so you don't know when to shrink. But counting subarrays with at most K distinct values is easy: for each right, every window from left to right is valid, adding right − left + 1 subarrays.

Subarrays with exactly K = (at most K) − (at most K − 1). Two simple windows replace one hard one.

AtMostK.java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int atMost(int[] a, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, total = 0;
        for (int right = 0; right < a.length; right++) {
            count.merge(a[right], 1, Integer::sum);
            while (count.size() > k) {
                int out = a[left++];
                if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
            }
            total += right - left + 1;      // all windows ending at right
        }
        return total;
    }
    public static void main(String[] args) {
        int[] a = {1, 2, 1, 2, 3};
        System.out.println("at most 2: " + atMost(a, 2));
        System.out.println("exactly 2: " + (atMost(a, 2) - atMost(a, 1)));
    }
}

Output

at most 2: 12
exactly 2: 7

Remember

Track a formed/satisfied counter so validity is O(1).
Remove keys whose count drops to 0 when the map's size matters.
Exactly K = atMost(K) − atMost(K − 1).

Common mistakes

Leaving zero-count keys in the map, so size() overcounts distinct values.
Trying to count "exactly K" with a single window.

Command Palette

Windows with Counts and the "At Most K" Trick

1.Count maps and a "satisfied" counter

2.Exactly K = at most K − at most (K − 1)