Minimum Recolors to Get K Consecutive Black Blocks

Difficulty: Easy | Acceptance: 68.70% | Paid: No Topics: String, Sliding Window

You are given a string blocks consisting only of ‘W’ and ‘B’ where ‘W’ represents white and ‘B’ represents black. You are also given an integer k, which represents the number of consecutive black blocks we want to have.

In one operation, you can change a ‘W’ to a ‘B’.

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

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sliding Window

Examples

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 == blocks.length
1 <= n <= 100
blocks[i] is either 'W' or 'B'.
1 <= k <= n

Approach 1: Brute Force

Intuition Iterate through every possible window of size k in the string. For each window, count how many ‘W’ characters are present, as these represent the operations needed to turn that window entirely into ‘B’s. Track the minimum count found.

Steps

• Initialize min_ops to a large value (e.g., infinity or n).
• Iterate i from 0 to n - k (inclusive).
• For each i, iterate j from i to i + k - 1 to count ‘W’s in the current window.
• Update min_ops with the minimum value found.
• Return min_ops.

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        n = len(blocks)
        min_ops = float('inf')
        for i in range(n - k + 1):
            count = 0
            for j in range(i, i + k):
                if blocks[j] == 'W':
                    count += 1
            min_ops = min(min_ops, count)
        return min_ops

Complexity

• Time: O(n * k), where n is the length of the string. We iterate through n-k+1 windows, and for each, we scan k elements.
• Space: O(1), we only use a few variables for counting.
• Notes: Simple to implement but inefficient for very large k relative to n.

Approach 2: Sliding Window

Intuition Instead of recounting the ‘W’s for every new window from scratch, we can reuse the count from the previous window. When the window slides one step to the right, we remove the leftmost character and add the new rightmost character. We adjust the count of ‘W’s based on these two characters only.

Steps

• Calculate the number of ‘W’s in the first window (indices 0 to k-1). Store this as count and min_ops.
• Iterate i from k to n-1 (the index of the new character entering the window).
• If the character leaving the window (blocks[i-k]) is ‘W’, decrement count.
• If the character entering the window (blocks[i]) is ‘W’, increment count.
• Update min_ops with the minimum value between current min_ops and count.
• Return min_ops.

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

Complexity

• Time: O(n), we traverse the string once to initialize the window and once to slide it.
• Space: O(1), only a few integer variables are used.
• Notes: This is the optimal approach for this problem, significantly faster than brute force for larger inputs.