Keep the Window Valid: Most Common Plus a Budget
A path is laid with coloured tiles: red, red, green, red, blue, red, red (RRGRBRR). A painter may repaint at most one tile. What is the longest run of same-coloured tiles they can end up with? The window idea from the last lesson still works. The only new skill is writing down, in one line, what makes a window "valid".
The rule
A window is valid when its size minus its most common count fits the budget.
Inside any stretch of tiles, the cheapest way to make them all one colour is to keep the colour that already appears most and repaint the rest. So the repaints needed are size − count of the most common colour. If that number is at most k, the stretch can be made uniform. Everything else is the grow-and-shrink loop, with a dictionary of colour counts as the thing the window tracks:
def longest_after_repaints(tiles, k):
counts = {}
left = best = 0
for right, colour in enumerate(tiles):
counts[colour] = counts.get(colour, 0) + 1
while (right - left + 1) - max(counts.values()) > k: # too many repaints
counts[tiles[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestWith a handful of colours, max(counts.values()) is quick, so the whole run is one pass. Shrinking is safe for the usual reason: a shorter stretch inside a fixable one never needs more repaints.
The shortcut
This capstone is really a recognition checklist for the whole section. Reach for a sliding window when:
- the answer is a contiguous stretch, and
- validity is one line you can update as items enter and leave, and
- moving an edge only ever pushes one way: for a "longest" question, a valid window stays valid when it shrinks; for a "shortest" question, it stays valid when it grows.
A fixed length means a fixed window. If rule 3 fails, as with sums that can go negative, go back to prefix sums.
R, R, G, R
Size 4, most common is R with 3: one repaint needed, within budget. Best: 4.
The trap is writing the rule as "no more than k tiles of other colours" but counting against a fixed colour, say red. The best colour can change as the window moves; the most common count always picks the right one.
Drills
Answer fast — trust the rule.
With a budget of 1 repaint, is the window RRGR valid?
What does longest_after_repaints("RGBRGB", 1) return?
What does longest_after_repaints("RRGRBRR", 2) return?
Which problem should use prefix sums rather than a sliding window?
Remember
- A window is valid when its size minus its most common count fits the budget.
- Shortcut: contiguous, one-line validity, stays valid when it shrinks; then use a window.
- Trap: counting against a fixed colour instead of the most common one.