Minimum Recolors to Get K Consecutive Black Blocks

How it works

When sliding the window one position to the right, most of the count stays the same. We only need to subtract the contribution of the element leaving the window and add the contribution of the new element entering. This avoids recounting the entire window each time, reducing time from O(n*k) to O(n).

Steps

1. Count 'W' characters in the first window (positions 0 to k-1). Set this as the initial result.
2. Slide the window from position k to n-1:
   • If the element leaving (at position i - k) is 'W', decrement the count.
   • If the element entering (at position i) is 'W', increment the count.
   • Update res with the minimum count seen.
3. Return res.

Complexity

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

Things to watch for

Off-by-One in Window Boundaries

The sliding window must have exactly k elements. A common bug is using i <= len(blocks) - k vs i < len(blocks) - k + 1 incorrectly, causing either one too few or one too many windows to be checked. Trace through a small example like blocks = "WBB", k = 2 to verify your loop bounds.

Forgetting to Update Count When Sliding

When sliding the window, you must both remove the contribution of the element leaving the window and add the contribution of the element entering. Forgetting either update causes the count to drift from the actual number of white blocks in the current window.

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        count_w = 0
        for i in range(k):
            if blocks[i] == 'W':
                count_w += 1

        res = count_w
        for i in range(k, len(blocks)):
            if blocks[i - k] == 'W':
                count_w -= 1
            if blocks[i] == 'W':
                count_w += 1
            res = min(res, count_w)
        return res

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int count_w = 0;
        for (int i = 0; i < k; i++) {
            if (blocks[i] == 'W') {
                count_w++;
            }
        }

        int res = count_w;
        for (int i = k; i < blocks.size(); i++) {
            if (blocks[i - k] == 'W') {
                count_w--;
            }
            if (blocks[i] == 'W') {
                count_w++;
            }
            res = min(res, count_w);
        }
        return res;
    }
};