Minimum Recolors to Get K Consecutive Black Blocks — Easy Problem & Solution

Problem statement

blocks is a string of 'W' (white) and 'B' (black) blocks. One operation recolors a single white block black.

Return the minimum number of operations needed so that somewhere in the string there are k consecutive black blocks.

Example 1

Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation: Recoloring the three whites in positions 3, 4 and 7 leaves a run of seven blacks.

Example 2

Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation: "BB" is already there.

Example 3

Input: blocks = "WWWW", k = 4
Output: 4

Constraints

• 1 <= k <= blocks.length <= 100
• blocks[i] is either 'W' or 'B'.

How to solve Minimum Recolors to Get K Consecutive Black Blocks

Any answer is realised by one window of length k, and that window costs exactly its number of white blocks. So minimise the white count over all fixed-size windows.

Approach

1. Count the whites in blocks[0 … k-1].
2. Slide: when the window advances, add the entering character if it is 'W' and subtract the leaving one if it was.
3. Return the smallest count seen.

Why it works

Recoloring is only ever useful inside the chosen window, and each white there must be recolored exactly once, so the window's white count is its exact cost. Taking the minimum over all windows is therefore the answer.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Recounting each window is O(n · k) — fine at n = 100 but the wrong habit.
• Initialising the best to 0 instead of the first window's count returns 0 always.
• Blacks are never recolored, so only 'W' contributes.

Reference solution

Python

def minimumRecolors(blocks: str, k: int) -> int:
    whites = blocks[:k].count("W")
    best = whites
    for i in range(k, len(blocks)):
        if blocks[i] == "W":
            whites += 1
        if blocks[i - k] == "W":
            whites -= 1
        best = min(best, whites)
    return best

JavaScript

var minimumRecolors = function(blocks, k) {
    var whites = 0;
    for (var i = 0; i < k; i++) if (blocks.charAt(i) === "W") whites++;
    var best = whites;
    for (var j = k; j < blocks.length; j++) {
        if (blocks.charAt(j) === "W") whites++;
        if (blocks.charAt(j - k) === "W") whites--;
        if (whites < best) best = whites;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Original Typed String I Easy
• Rearrange Characters to Make Target String Easy
• Number of Strings That Appear as Substrings in Word Easy
• Circular Sentence Easy
• Number of Senior Citizens Easy
• Find Words Containing Character Easy