Sliding windows with counts

A sliding window is a pair of pointers marking a contiguous range in a string or array. Moving the right pointer forward adds elements to the window; moving the left pointer forward removes them. Solving a problem this way costs O(N) total, instead of the O(N²) it takes to check every one of the O(N²) possible subarrays directly.

When a window holds letters or other discrete items, you usually need their counts, not just their presence. An array of 26 integers, one slot per letter a–z, tracks exactly how many times each letter appears in the current window, and answers questions like "does this window have exactly three vowels?" in O(1), without rescanning the window.

Fixed-length windows

Some problems ask about every substring of a fixed length K: does it match a target pattern, does it have exactly three vowels, and so on.

Start with the first K characters as the window, and compute whatever property matters. Then slide forward one character at a time: drop the leftmost character, add the new rightmost one, update the counts, and check the property again. The window always holds exactly K characters; only its position moves.

Take "abcdefgh" and ask which length-5 substrings are permutations of "abcde." The first window, "abcde," matches. Sliding right gives "bcdef," which holds b, c, d, e, f instead of a, b, c, d, e, so it does not match. The process keeps sliding one step at a time until the string runs out.

Using a matches counter

Comparing two full count arrays on every slide works, but it costs O(26) per step just to check equality. A matches counter avoids that: instead of comparing every count, track how many of the 26 letters currently have the count they are supposed to have.

Say you want windows matching the target counts {a: 1, b: 1, c: 1, d: 1, e: 1}. Build target_count and window_count, both arrays of size 26, and set matches to how many of the 26 letters already agree between them. At the very start, every letter has count 0 in the empty window, and 21 of the 26 target counts are also 0, so matches starts at 21.

Sliding the window updates matches incrementally. Adding a letter increments its window count, and then increments matches if that new count now equals the target, or decrements matches if the count used to equal the target and no longer does. Removing a letter runs the same check in the other order: decrement matches if the current count still equals the target, decrement the count, then increment matches if the new, lower count equals the target. The window matches the target completely exactly when matches reaches 26, meaning every one of the 26 letters, including the ones the target wants at zero, has the right count. This keeps every update O(1), with no full-array comparison anywhere in the loop.

Variable-length windows

Some problems do not fix the window length at all; instead, the window grows and shrinks to maintain a property as you scan.

Finding the longest substring with at most K distinct letters is the standard example. Move the right pointer to grow the window. The moment the window holds more than K distinct letters, move the left pointer forward, shrinking the window, until it is back down to K distinct letters or fewer. Every character is still added and removed at most once across the whole scan, so the total cost stays O(N) even though the window's length keeps changing.

A worked example

Find the longest substring with at most 3 distinct characters. Keep a count of each character in the window, and a distinct counter for how many characters currently have a nonzero count. Grow the window from the right; the moment distinct exceeds 3, shrink from the left until it is 3 again, and track the longest window seen so far.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    s = input_data[0]10    k = int(input_data[1])11
12    if not s:13        print(0)14        return15
16    counts = [0] * 2617    distinct = 018    left = 019    max_len = 020
21    for right in range(len(s)):22        char_idx = ord(s[right]) - ord('a')23        if counts[char_idx] == 0:24            distinct += 125        counts[char_idx] += 126
27        while distinct > k:28            left_char_idx = ord(s[left]) - ord('a')29            counts[left_char_idx] -= 130            if counts[left_char_idx] == 0:31                distinct -= 132            left += 133
34        max_len = max(max_len, right - left + 1)35
36    print(max_len)37
38
39if __name__ == "__main__":40    main()

aabbbcccc 2

7

Trace it on "aabbbcccc" with K = 2. The window grows freely through a, aa, aab, aabb, aabbb, since it never holds more than 2 distinct letters, and the longest window so far reaches 5. Adding the first c pushes distinct letters to 3, so the left pointer shrinks the window, dropping both as, down to bbbc, which is back to 2 distinct letters (b and c). From there the window keeps growing as more cs arrive: bbbcc, bbbccc, bbbcccc, each still holding only b and c, and the longest window grows right along with it, ending at 7. The program prints 7, matching the window "bbbcccc", not the shorter run of as and bs seen earlier in the scan.

Optimizing with arrays

In the hot loop, count with a plain list, not a dictionary; array indexing beats dictionary lookup, and the gap matters on PyPy where this loop runs millions of times. For letters, counts = [0] * 26 indexed by ord(char) - ord('a') is the standard setup. collections.Counter is convenient outside the inner loop, but inside it, a plain list is consistently faster.

Recognizing which window you need

A fixed-length window fits questions about every substring of exactly length K: slide it one character at a time, updating counts as you add and remove. A variable-length window fits questions where the property itself defines the window's size, such as "at most K distinct characters" or "sum at most a target": grow from the right, shrink from the left, and let the property decide when to do which. A matches counter is not a different kind of window, it is a way to check a window's property in O(1) instead of O(26): track how many counts currently agree with a target, rather than recomparing every count on every step.

These three pieces cover most senior-level sliding window problems, whether the question is about substring matching, subarray sums, or a limit on how many distinct values a window may hold.