Sliding Window
Fixed-size windows and matching
When the width never changes, the window becomes a rolling comparison against a target.
Key idea
One in, one out
When the window width is fixed, there is no shrink loop. Every step adds exactly one element on the right and removes exactly one on the left, so the state update is two operations regardless of how wide the window is.
That is what makes fixed windows cheap. Recomputing from scratch would cost the window width per step; rolling costs a constant.
Gotcha
The two boundary checks are different
right >= width decides when an element starts leaving. right >= width - 1 decides when the window is first full and a result should be recorded. They are off by one from each other and swapping them is a classic error.
Sanity check with the first full window: for width 3 the window is full at right == 2, and nothing has left yet because only 3 elements have entered. So recording starts at 2 and removing starts at 3.
Key idea
Comparing the window to a target
Fixed windows are often paired with a question of the form: does this window match some target description? The description is usually a count map, and matching means the two maps agree.
Comparing two dicts on every step costs the alphabet size per step, which is a constant and perfectly acceptable. There is also a cheaper trick worth knowing.
Why it works
Tracking how many letters already agree
Instead of comparing whole maps, keep a single number: how many distinct characters currently have exactly the right count. When that number equals the number of distinct characters in the target, the window matches.
Update it whenever a count changes. If a count just became equal to its target, the number goes up. If it just moved away from equal, the number goes down. The subtlety is that a single change can only affect the one character whose count changed, so the update is constant time.
Tip
Recovering the start index
With right inclusive and a fixed width, the window starts at right - width + 1. That expression appears constantly in fixed-window code and is worth being able to write without thinking.
Check it on the first full window: right is width - 1, so the start is 0. Correct.
What the problem below needs
The problem asks whether any window of a fixed width matches a target exactly, where exactly means the same characters with the same counts. You know how to roll a fixed window, you know how to build a count map, and you know from Unit 1 that two count maps compare equal when their contents agree. Put those together.
Rolling comparisons
averages_of_width returns the average of every window of the given width, rolling the total rather than resumming. first_window_with_all_distinct returns the start index of the first window of the given width whose characters are all distinct, or -1. matches_target_counts reports whether a window of text starting at start has exactly the character counts given in target.
Tests
print(averages_of_width([1, 2, 3, 4], 2))
print(first_window_with_all_distinct("abcabc", 3), first_window_with_all_distinct("aaaa", 2))
print(matches_target_counts("abcb", 1, {"b": 2, "c": 1}), matches_target_counts("abcb", 0, {"b": 2, "c": 1}))Output
Run the tests when you are ready.
Permutation In String
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.