Sliding Window
When validity is a computed quantity
Sometimes the window is legal or not based on a number you have to derive rather than read.
A window with a budget
In the last lesson, legality was something you could read directly: a total, a count of distinct characters. Now consider a window that is allowed a limited number of changes.
The concrete version: given a list of 0s and 1s, and a budget of k flips from 0 to 1, what is the longest stretch you can make all 1s?
Why it works
What does the budget buy?
The window is legal when the number of 0s inside it is at most k, because each 0 costs one flip. So the state to carry is a count of zeros, and the rule is a comparison against k.
That is the whole derivation, and it is worth doing explicitly on paper for any problem of this shape. The mechanics are already known; the question is always what quantity the budget is being spent on.
Key idea
When the cost depends on the contents
The version above is easy because the thing being changed is fixed: every 0 costs one flip. It gets more interesting when you get to choose what to change the window into, and the cost depends on that choice.
Suppose a window may have up to k characters replaced, and you want every character in it to end up the same. Which character should the others become? Obviously the one that already appears most often, since that requires the fewest replacements.
So the number of replacements needed is the window size minus the count of the most frequent character inside it. The window is legal when that difference is at most k.
Why it works
The formula to remember
replacements needed = window size - count of the most common character in the window.
Everything else follows. Carry a count map for the window, take the largest count in it, and compare the difference to the budget. That is the entire problem below, expressed as one sentence, and deriving that sentence is the work.
Tip
A subtlety about the maximum count
Recomputing the largest count from the map on every step costs an extra factor for the alphabet size, which is fine and passes comfortably. Many published solutions instead keep a running maximum that is never decreased when the window shrinks.
That looks wrong and is not. A stale maximum can only make the window look less legal than it is, so the loop never accepts an illegal window. And a larger answer is only ever recorded when the true maximum genuinely grows, which does update the running value.
Use whichever you can justify under pressure. The recompute version is easier to defend and rarely too slow.
Gotcha
Shrink with `while`, not `if`, unless you mean it
Some window solutions use if instead of while so the window never actually shrinks, only slides. That is correct when you only want the maximum length, because a window that stops growing still tracks the best length seen.
It is wrong whenever you need the window's contents to be legal at every step, such as when counting windows or reporting one. Know which of those you are doing before choosing the keyword.
How many replacements does this window need?
A window holds the characters AABABBA and you may replace characters to make them all identical. How many replacements does it need, and how is that computed?
Find the window bug
This is meant to find the longest stretch with at most k zeros. It reports windows that are too long. Click the line that is wrong.
This activity type is not wired up yet.
Cost of the flip window
Time and space for longest_all_ones_after_flips on a list of n bits.
Time
Space
Longest Repeating Character Replacement
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.