2379. Minimum Recolors to Get K Consecutive Black Blocks Easy

You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the i^th block. The characters 'W' and 'B' denote the colors white and black, respectively.

You are also given an integer k, which is the desired number of consecutive black blocks.

In one operation, you can recolor a white block such that it becomes a black block.

Return the minimum number of operations needed such that there is at least one occurrence of k consecutive black blocks.

Example 1:
Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks so that they become black.
This yields blocks = "BBBBBBBWBW".
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.

Example 2:
Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation:
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.

Approach

Input: A string blocks containing only 'W' and 'B', and an integer k

Output: The minimum number of operations to turn any substring of length k entirely to 'B's, where each operation turns a 'W' into a 'B'

This problem belongs to the Fixed-length Sliding Window category.

We can use a sliding window of length k to count the number of 'W's currently inside the window because every 'W' requires exactly one sequence operation to become 'B'. The number of 'W's in our window directly corresponds to the number of operations needed to turn that entire substring into 'B's.

Initially, count the number of 'W's in the first k characters. Then, slide the window to the right, one character at a time:

• When removing the leftmost character from the window, if it is 'W', decrement our operations count;
• When adding the new rightmost character into the window, if it is 'W', increment our operations count;
• At each step, update the minimum operations count seen so far.

Finally, return the absolute minimum count recorded across the entire traversal.

Implementation

python

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        left = 0
        white_count = 0  # Frequency of 'W' inside the current window

        # Initialize the first window
        for i in range(k):
            if blocks[i] == 'W':
                white_count += 1

        min_ops = white_count  # Keep track of minimum operations required

        # Traverse with our sliding window, starting from the k-th character
        for right in range(k, len(blocks)):
            # If the block sliding out of the window is white, decrement white count by 1
            if blocks[left] == 'W':
                white_count -= 1

            # If the block sliding into the window is white, increment white count by 1
            if blocks[right] == 'W':
                white_count += 1

            left += 1  # Shift left pointer to the right to slide the window forward

            # Update the minimal operation occurrences recorded globally against this window metric
            min_ops = min(min_ops, white_count)

        return min_ops  # Final answer returned dictating the fewest changes necessary globally

javascript

var minimumRecolors = function(blocks, k) {
    let count = 0;

    for (let i = 0; i < k; i++) {
        if (blocks[i] === 'W') count++;
    }

    let ans = count;
    let left = 0;
    for (let right = k; right < blocks.length; right++) {
        if (blocks[right] === 'W') count++;

        if (blocks[left] === 'W') count--;

        left++;
        ans = Math.min(ans, count);
    }

    return ans;
};

Complexity Analysis

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

Links

2379. Minimum Recolors to Get K Consecutive Black Blocks (English)2379. 得到 K 个黑块的最少涂色次数 (Chinese)