Counting Windows and the Window Maximum

Sliding Window, lesson 3 of 3

Counting Windows and the Window Maximum

Track letter counts, turn "exactly k" into "at most k", and preview the monotonic deque.

13 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Many string windows care about how many of each character are inside. A Counter (or a list of 26 ints for lowercase letters) is the window's memory: += 1 when a character enters, -= 1 when it leaves.

One trap: after count[ch] -= 1 hits zero the key is still there, so len(count) still counts it. Delete zero keys when you use len() to mean "distinct items in the window".

Quiz

What does this print?

Example

Distinct values in every window of size k

Fixed-size window, but the "sum" is now a Counter. Comment out the del line and watch the numbers go wrong.

Comparing a window with a target. "Does some window of s use exactly the letters of p?" Keep need (counts of p) and have (counts in the window, which has size len(p)). With 26-slot lists, have == need costs O(26) = O(1) per step.

For "shortest window that covers t" (Minimum Window Substring) track one more number, formed: how many distinct characters currently have have[c] >= need[c]. The window is valid exactly when formed == len(need), and you update formed only when a count crosses that line, so the check stays O(1).

Exercise

Find all anagram windows

Write find_anagrams(s, p) that returns the start index of every substring of s that is an anagram of p (same letters, same counts, any order), in increasing order. Both strings are lowercase letters.

Slide a window of size len(p) and compare letter counts.

find_anagrams("cbaebabacd", "abc")  -> [0, 6]
find_anagrams("abab", "ab")         -> [0, 1, 2]

"Exactly k" is hard, "at most k" is easy. Count subarrays with exactly k distinct values? A window can't answer that directly: shrinking can move you from "exactly k" to "fewer than k" and back. But "at most k" is monotonic, and each right adds right - left + 1 new valid subarrays (all the ones ending at right). Then:

exactly(k) = at_most(k) - at_most(k - 1)
Example

Subarrays with exactly k distinct values

The 7 subarrays with exactly 2 distinct values are [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2] and [1,2,1,2].

Preview: the window maximum. A running sum can "subtract" the element that leaves, but a maximum can't: when the max leaves, what's next? Re-scanning the window is O(k) per step.

The fix is a monotonic deque of indices whose values are decreasing from front to back:

  • Before pushing i, pop smaller-or-equal values off the back. They can never be a max again, because nums[i] is at least as big and leaves later.
  • Pop the front if its index has slid out of the window.
  • The front is always the window's max.

Each index is pushed and popped at most once, so it's O(n) overall. You'll use it in Sliding Window Maximum, and again in the Stacks unit.

Example

Window max with a monotonic deque

The deque never holds more than k indices and its front is always the answer for the current window.

Quiz

What does this print?

Quiz

You need the number of subarrays whose sum is exactly k, and nums may contain negatives. Best tool?