Problem Informations

• Problem Index: 2379
• Problem Link: Minimum Recolors to Get K Consecutive Black Blocks
• Topics: String, Sliding Window

Problem Description

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 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.

Constraints:

• $n == \text{blocks.length}$
• $1 \leq n \leq 100$
• $blocks[i]$ is either 'W' or 'B'.
• $1 \leq k \leq n$

Intuition

The problem involves transforming a string of blocks into a sequence that has at least k consecutive black blocks, where each block can either be black 'B' or white 'W'. The allowed operation is to recolor a white block to a black block, and the goal is to minimize the number of such operations. This can be viewed as a classic sliding window problem, where we wish to find the window of length k that has the maximum number of black blocks already present. From this information, we can determine how many recoloring operations are necessary to achieve the desired sequence.

Approach

The approach leverages a sliding window technique to efficiently calculate the minimum number of recoloring operations. The key steps are as follows:

1. Initialize Black Count: Start by counting the number of black blocks in the first window of size k. This will help set up our initial window and calculate the number of operations needed for it.

2. Calculate Initial Operations: Determine the initial number of operations needed to convert this first window into a sequence of k consecutive black blocks by subtracting the number of black blocks in the window from k.

3. Slide the Window: Slide the window across the string one block at a time. For each step:

   • Include the next block into the window and update the count of black blocks.
   • Exclude the previous block from the window and update the count of black blocks accordingly.
   • Recalculate the minimum operations needed for the current window to achieve k consecutive black blocks by determining how many white blocks are present in the window.

4. Update Minimum Operations: Continuously update the minimum number of operations found as the window slides across the string.

5. Return Result: After the window has traversed the whole string, the stored minimum operations count will be the answer to the problem.

This approach ensures that we efficiently find the window where the least number of recoloring operations are required, thereby solving the problem with minimal computational overhead.

Code

C++

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int blackCount = 0;

        // Count the number of black blocks in the first window of size k
        for (int i = 0; i < k; i++) {
            if (blocks[i] == 'B') {
                blackCount++;
            }
        }

        // The initial answer is the number of white blocks in the first window
        int minOperations = k - blackCount;

        // Slide the window across the string
        for (int i = 0; i < blocks.size() - k; i++) {
            // Include the next block in the window
            if (blocks[i + k] == 'B') {
                blackCount++;
            }

            // Exclude the previous block from the window
            if (blocks[i] == 'B') {
                blackCount--;
            }
            
            // Update the minimum operations required to achieve k consecutive black blocks
            minOperations = min(minOperations, k - blackCount);
        }

        return minOperations;
    }
};

Python

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        blackCount = 0

        # Count the number of black blocks in the first window of size k
        for i in range(k):
            if blocks[i] == 'B':
                blackCount += 1

        # The initial answer is the number of white blocks in the first window
        minOperations = k - blackCount

        # Slide the window across the string
        for i in range(len(blocks) - k):
            # Include the next block in the window
            if blocks[i + k] == 'B':
                blackCount += 1

            # Exclude the previous block from the window
            if blocks[i] == 'B':
                blackCount -= 1
            
            # Update the minimum operations required to achieve k consecutive black blocks
            minOperations = min(minOperations, k - blackCount)

        return minOperations

Complexity

• Time complexity: $O(n)$

  The algorithm uses a sliding window approach with a fixed window size of $k$. Initially, it counts the number of black blocks in the first window of size $k$. This operation takes $O(k)$. Then, the window is slid across the string from the next position until the end, requiring $O(n-k)$ operations to adjust the count of black blocks as the window moves. Thus, the total time complexity is $O(k) + O(n-k) = O(n)$.

• Space complexity: $O(1)$

  The algorithm uses a constant amount of additional space, regardless of the input size. It uses a few integer variables to keep track of counts and store the minimum number of operations needed. Therefore, the space complexity is $O(1)$.