174. Fewest Repaints
A row of toy blocks is described by the string blocks: the character 'B' is a black block and 'W' is a white block. A child wants to show off a run of k black blocks standing side by side.
In one repaint you may pick any single white block and paint it black. Return the smallest number of repaints needed so that at least one run of k consecutive blocks is entirely black. If such a run already exists, the answer is 0.
Example 1
- Input:
- blocks = "BWWBWBBW", k = 4
- Output:
- 1
- Explanation:
The window BWBB contains one white block, the fewest among all windows of length 4 (BWWB has 2, WWBW has 3, WBWB has 2, WBBW has 2), so one repaint is enough.
Example 2
- Input:
- blocks = "WWWW", k = 2
- Output:
- 2
- Explanation:
Every window of length 2 is entirely white, so both blocks of some window must be repainted: 2.
Constraints
1 ≤ k ≤ blocks.length ≤ 105
blocks[i] is either 'B' or 'W'.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)