699. Fewest Repaints for a Run of k
A row of blocks is given as a string of B and W. Repainting one block costs one move.
Print the fewest moves needed to make some k CONSECUTIVE blocks all B.
WBBWWBBWBW, k = 7 -> 3
WBWBBBW, k = 2 -> 0
WWWW, k = 2 -> 2
## The window never changes size
Every other problem in this topic grows and shrinks a window to keep an invariant. Here the
window is exactly k wide from the first step to the last, because the question already
fixed it.
The cost of making a given window all B is simply how many W it holds, so the answer is
the SMALLEST number of W in any window of length k.
## Slide, do not recount
Build the count for the first window, then move one step at a time:
w = number of W in s[0 .. k-1]
best = w
for i in k .. n-1:
if s[i] == 'W': w += 1
if s[i - k] == 'W': w -= 1
best = min(best, w)
One value enters and one leaves per step, which is the entire idea behind a fixed window: the
quantity is repaired in O(1) rather than rebuilt in O(k).
Recounting each window is O(n * k) and is the difference between passing and timing out at
n = 200000.
## The order of the two updates
Add the entering block before removing the leaving one, or use separate reads as above. Writing
w += (s[i] == 'W') - (s[i-k] == 'W') in one expression is fine; reusing a single variable for
both tests is not.
## Relationship with problem 111
111 slides a fixed window keeping its SUM and takes the maximum. This keeps a COUNT and takes the minimum. The mechanics are identical, and recognising that is worth more than either problem alone.
## Boundaries
k = n leaves exactly one window. A row that is already all B answers 0. A row of all W
answers k.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ k ≤ length of the row ≤ 200000` - every character is `B` or `W`
Input
The first line contains an integer k.
The second line contains the row, a string of B and W.
Output
Print one integer, the fewest repaints.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.