Minimum Recolors to Get K Consecutive Black Blocks
Easy · Sliding Window · String · Sliding Window
Problem
You are given a string blocks in which each character is 'W' (a white block) or 'B' (a black block), and an integer k.
In one operation you may repaint a single white block black. Return the minimum number of operations needed so that some run of k consecutive blocks is entirely black.
Examples
Input: blocks = "BWBWWB", k = 3 Output: 1
The window BWB at the start has one white block, and no window of three is all black, so one repaint is needed.
Input: blocks = "BBBB", k = 2 Output: 0
Any two neighbors are already black, so no repaint is needed.
Input: blocks = "WBWBBBW", k = 7 Output: 3
The run must cover all seven blocks, so all three whites are repainted.
Constraints
- 1 <= blocks.length <= 100
- blocks[i] is 'W' or 'B'
- 1 <= k <= blocks.length
Approaches
- Baseline: count every window from scratch — time O(n·k), space O(1)
Follow-up
The fixed window works because every candidate run has the same length. The use cases change that: when each white block has its own repaint cost the window sums costs instead of counting, and when the question becomes the shortest window holding at least t black blocks, the window length varies and two pointers take over.
Related problems
Start free on Cariara · Coding problems · System design studio
