Fewest Repaints for a Dark Run
EasySliding Window
Problem
A fence is a row of boards described by blocks: 'B' is a board already painted black and 'W' a white board. You want `k` consecutive black boards somewhere along the fence.
Each repaint turns one white board black. Return the minimum number of repaints needed.
Example 1
- Input:
- blocks = "BWWBBWB", k = 4
- Output:
- 1
The last four boards "BBWB" contain one white board; every other window of four has two.
Example 2
- Input:
- blocks = "WWW", k = 2
- Output:
- 2
Constraints
- 1 ≤ k ≤ blocks.length ≤ 10^5
- blocks[i] is 'B' or 'W'.
Hint
Show the first hint
Any window of length k can be made fully black. What does it cost?
Walkthrough
How to approach it
01Clarify before coding
- Can I repaint a black board white? It never helps, so only W → B repaints matter.
- Must the run be exactly k? At least k, but any longer run contains a run of exactly k, so looking at windows of length k is enough.
- Is k ≤ length guaranteed? Yes.
02Brute force
For each start, count the whites among the next k boards and keep the minimum.
Cost: O(n·k) time; up to 2.5·10^9 checks when k is about n/2.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.