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 cheatsheetGetting 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".
What does this print?
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).
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)
Counting subarrays with at most 2 distinct values
Add 1. One subarray ends here: [1]. total = 1.
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, becausenums[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.
Window max on [1, 3, 1, 2, 0, 5], k = 3
Push index 0 (value 1). Window not full yet.
The deque row holds indices into nums, front on the left. Their values decrease from front to back.
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.
What does this print?
You need the number of subarrays whose sum is exactly k, and nums may contain negatives. Best tool?