Code Logo

Minimum Recolors To Get K Consecutive Black Blocks

Published at16 Mar 2026
Created by
Easy 6 views
Like0

You are given a string of block colors made of 'B' and 'W', and you want to create a contiguous run of exactly k black blocks.

You are allowed to recolor white blocks into black, and the question is: what is the smallest number of recolors needed? So you are not searching for the longest black run overall. You are checking every window of size k and asking how many white blocks inside that window would need to be flipped.

For example, if blocks = "WBBWWBBWBW" and k = 7, the best length-7 window still contains 3 white blocks, so the answer is 3. If blocks = "WBWBBBW" and k = 2, the answer is 0 because the window "BB" already works without any recoloring.

So the task is to find the size-k window with the fewest white blocks, because those are exactly the blocks that would need recoloring.

Example Input & Output

Example 1
Input
blocks = "WBBWWBBWBW", k = 7
Output
3
Explanation

Best size-7 window contains 3 white blocks.

Example 2
Input
blocks = "WBWBBBW", k = 2
Output
0
Explanation

Window "BB" already satisfies the requirement.

Example 3
Input
blocks = "WWWW", k = 2
Output
2
Explanation

Need to recolor both blocks in any window.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Recolors To Get K Consecutive Black Blocks
Recommendation Algorithm Flow for Minimum Recolors To Get K Consecutive Black Blocks

Solution Approach

This is another fixed-size sliding window problem. The thing we care about inside each window is not the number of black blocks directly, but the number of white blocks. That is because each white block in the chosen window represents one recolor we must perform to turn the entire window black.

So the problem becomes: among all windows of length k, find the one with the fewest 'W' characters.

Start by counting the white blocks in the first window of size k. That gives the initial recolor cost for that window, and it is also our first candidate answer.

Then slide the window one position at a time. Each move removes one character from the left and adds one character on the right. If the outgoing character is 'W', subtract one from the white count. If the incoming character is 'W', add one. After each update, compare the current white count with the minimum seen so far.

This is much faster than recounting every window from scratch. A brute-force method would count whites separately for every size-k substring, but the sliding-window version only adjusts for the two characters that changed.

Another way to think about it is that every window is already a candidate block segment. We are not choosing which individual blocks to recolor globally. We are only asking: if this exact segment became the target run, how many white blocks inside it would need to change?

This viewpoint also explains why the answer can never be negative and can never exceed k. In the best case, the window already contains all black blocks and needs 0 recolors. In the worst case, all k positions are white and every one of them must be flipped.

The runtime is O(n) and the extra space is O(1). The real trick is recognizing that "minimum recolors" is exactly the same thing as "minimum number of white blocks inside any window of length k." Once that is clear, the sliding-window pattern becomes very direct.

Best Answers

java
class Solution {
    public int minimum_recolors_to_get_k_consecutive_black_blocks(String blocks, int k) {
        int n = blocks.length();
        if (k <= 0 || k > n) return 0;
        int white = 0;
        for (int i = 0; i < k; i++) if (blocks.charAt(i) == 'W') white++;
        int best = white;
        for (int i = k; i < n; i++) {
            if (blocks.charAt(i) == 'W') white++;
            if (blocks.charAt(i-k) == 'W') white--;
            if (white < best) best = white;
        }
        return best;
    }
}