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? For a fixed right, the starts that work sit in a middle stretch (further left: more than k; further right: fewer than k), so one window can't count them. "At most k" has no such problem: if nums[left..right] is valid, so is every shorter subarray ending at right. Each right therefore adds right - left + 1 valid subarrays (one per start from left to right). Then:

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

Counting subarrays with at most 2 distinct values

1212301234+1left, right
Step 1 of 6
count = {1: 1}
total = 1

Add 1. One subarray ends here: [1]. total = 1.

subarrays ending at right
just added
out of the window
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.

Walkthrough

Window max on [1, 3, 1, 2, 0, 5], k = 3

nums131205012345ideque00out
Step 1 of 7
deque values = [1]

Push index 0 (value 1). Window not full yet.

window
front = window max
waiting in the deque

The deque row holds indices into nums, front on the left. Their values decrease from front to back.

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. Try [1, 3, -1, -3, 5, 3, 6, 7]: there, every max is popped from the back before it can slide out.

Quiz

What does this print?

Quiz

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