Minimum Recolors to Get K Consecutive Black Blocks

easy sliding window string two pointers

Problem

You are given a string blocks of 'W' (white) and 'B' (black) characters, and an integer k. In one operation you may recolor a white block to black. Return the minimum number of operations so that there is at least one run of k consecutive black blocks.

Inputblocks = "WBBWWBBWBW", k = 7

Output3

The window blocks[0..6] = "WBBWWBB" has 3 whites; recoloring them gives 7 black blocks. No window of size 7 has fewer whites.

Inputblocks = "WBWBBBW", k = 2

Output0

The window "BB" already has 2 consecutive black blocks, so no recolors are needed.

blocks (W / B characters)

k (window size)

def min_recolors(blocks, k):
    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

function minRecolors(blocks, k) {
  let whites = 0;
  for (let i = 0; i < k; i++) if (blocks[i] === 'W') whites++;
  let best = whites;
  for (let i = k; i < blocks.length; i++) {
    if (blocks[i] === 'W') whites++;
    if (blocks[i - k] === 'W') whites--;
    best = Math.min(best, whites);
  }
  return best;
}

int minRecolors(String blocks, int k) {
    int whites = 0;
    for (int i = 0; i < k; i++)
        if (blocks.charAt(i) == 'W') whites++;
    int best = whites;
    for (int i = k; i < blocks.length(); i++) {
        if (blocks.charAt(i) == 'W') whites++;
        if (blocks.charAt(i - k) == 'W') whites--;
        best = Math.min(best, whites);
    }
    return best;
}

int minRecolors(string blocks, int k) {
    int whites = 0;
    for (int i = 0; i < k; i++)
        if (blocks[i] == 'W') whites++;
    int best = whites;
    for (int i = k; i < (int)blocks.size(); i++) {
        if (blocks[i] == 'W') whites++;
        if (blocks[i - k] == 'W') whites--;
        best = min(best, whites);
    }
    return best;
}

Explanation

Any run of k consecutive black blocks must occupy some window of exactly k contiguous positions. To turn that window all-black, we must recolor every white block inside it — so the cost of a window equals its number of white blocks. The answer is the smallest such cost over all windows.

There are n - k + 1 windows. Counting whites from scratch for each one would be O(n·k). Instead we use a fixed-size sliding window that updates the white count in O(1) as it slides.

First we count the whites in the initial window blocks[0..k-1] and store it as best. Then we slide one step at a time: index i enters on the right (if it is 'W', increment whites) and index i - k leaves on the left (if it was 'W', decrement whites).

After each slide, whites is the white count of the current window, so we update best = min(best, whites). Each block is added and removed exactly once, giving overall O(n) time and O(1) extra space.

Example: blocks = "WBBWWBBWBW", k = 7. The first window "WBBWWBB" has 3 whites; sliding to "BBWWBBW" gives 3, "BWWBBWB" gives 3, "WWBBWBW" gives 4. The minimum is 3.

Time: O(n) Space: O(1)