LeetCode 2379 - Minimum Recolors to Get K Consecutive Black Blocks

LeetCode Problem 2379

Difficulty: 🟢 Easy
Topics: String, Sliding Window

Solution

Problem Understanding

The problem gives us a string called blocks, where each character represents the color of a block. A character 'B' means the block is black, and a character 'W' means the block is white.

We are also given an integer k. Our goal is to make sure there exists at least one group of exactly k consecutive blocks that are all black.

The only operation allowed is recoloring a white block into a black block. Black blocks already satisfy the requirement, so they never need modification. We need to compute the minimum number of recoloring operations required.

In other words, we must examine every contiguous substring of length k and determine how many white blocks appear inside it. Since every white block in that window must be recolored to black, the number of white blocks directly equals the number of operations needed for that window. The answer is the minimum such value across all windows of size k.

The constraints are small:

• 1 <= n <= 100
• 1 <= k <= n

Since the input size is tiny, even relatively inefficient approaches would work. However, the problem is designed to teach the sliding window technique, which gives a clean and optimal solution.

Some important edge cases include:

• When the string already contains k consecutive black blocks, the answer should be 0.
• When all blocks are white, every block in the chosen window must be recolored.
• When k == 1, we only need one black block somewhere in the string.
• When k == n, the entire string becomes one single window.
• Windows at the beginning or end of the string must be handled correctly without index errors.

Approaches

Brute Force Approach

The brute force solution checks every possible substring of length k.

For each starting position:

1. Extract the window of length k.
2. Count how many characters are 'W'.
3. Track the minimum count seen so far.

This works because every valid group of k consecutive blocks corresponds to exactly one substring of length k. Counting white blocks tells us how many recoloring operations are needed for that substring.

Although this approach is straightforward, it repeatedly scans overlapping windows. If we recompute the white count from scratch for every window, we do unnecessary repeated work.

The time complexity becomes O(n * k) because there are O(n) windows and each window requires O(k) work.

Optimal Sliding Window Approach

The key observation is that adjacent windows overlap heavily.

Suppose we already know the number of white blocks in one window. When shifting the window one position to the right:

• One character leaves the window.
• One new character enters the window.

Instead of recounting everything, we can update the white count incrementally:

• If the outgoing character is white, decrement the count.
• If the incoming character is white, increment the count.

This is exactly what the sliding window technique is designed for.

The sliding window approach processes each character at most twice, once when entering the window and once when leaving it. This reduces the time complexity to O(n) while using only O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Recounts white blocks for every window
Optimal	O(n)	O(1)	Uses a sliding window to update counts incrementally

Algorithm Walkthrough

1. Initialize a variable white_count to store the number of white blocks in the current window.
2. Compute the number of white blocks in the first window of size k.
3. Initialize the answer variable minimum_operations with this first window count. This represents the best answer seen so far.
4. Start sliding the window from left to right.
5. For every shift:

• Remove the contribution of the outgoing character.
• Add the contribution of the incoming character.
• Update minimum_operations if the current window has fewer white blocks.

6. Continue until all windows of size k have been processed.
7. Return minimum_operations.

Why it works

Every valid solution corresponds to choosing some contiguous window of length k. The number of recolors needed for that window equals the number of white blocks inside it.

The sliding window always maintains the exact white block count for the current window. Since every possible window is examined exactly once, and we keep the minimum white count among them, the algorithm correctly returns the minimum number of recoloring operations needed.

Python Solution

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

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

        minimum_operations = white_count

        # Slide the window
        for right in range(k, len(blocks)):
            left = right - k

            # Remove outgoing character
            if blocks[left] == 'W':
                white_count -= 1

            # Add incoming character
            if blocks[right] == 'W':
                white_count += 1

            minimum_operations = min(minimum_operations, white_count)

        return minimum_operations

The implementation begins by counting the number of white blocks in the first window of size k. This establishes the initial state of the sliding window.

The variable minimum_operations stores the smallest number of white blocks encountered so far. Since each white block requires one recoloring operation, this variable directly represents the answer.

The second loop slides the window across the string. The outgoing character is located at index left, while the incoming character is located at index right.

Whenever a white block leaves the window, the count decreases. Whenever a white block enters the window, the count increases.

After updating the window, the algorithm compares the current white count with the best answer seen so far.

At the end, the minimum number of required recolors is returned.

Go Solution

func minimumRecolors(blocks string, k int) int {
    whiteCount := 0

    // Count white blocks in the first window
    for i := 0; i < k; i++ {
        if blocks[i] == 'W' {
            whiteCount++
        }
    }

    minimumOperations := whiteCount

    // Slide the window
    for right := k; right < len(blocks); right++ {
        left := right - k

        // Remove outgoing character
        if blocks[left] == 'W' {
            whiteCount--
        }

        // Add incoming character
        if blocks[right] == 'W' {
            whiteCount++
        }

        if whiteCount < minimumOperations {
            minimumOperations = whiteCount
        }
    }

    return minimumOperations
}

The Go implementation follows exactly the same logic as the Python solution.

Strings in Go can be indexed directly because the input contains only ASCII characters 'W' and 'B'. No rune conversion is necessary.

The solution uses only integer variables and constant extra space. Since the maximum string length is only 100, integer overflow is never a concern.

Worked Examples

Example 1

Input:

blocks = "WBBWWBBWBW"
k = 7

Initial window:

"WBBWWBB"

White blocks:

• Index 0 → W
• Index 3 → W
• Index 4 → W

So:

white_count = 3
minimum_operations = 3

Now slide the window.

Window	Outgoing	Incoming	White Count	Minimum
WBBWWBB	-	-	3	3
BBWWBBW	W	W	3	3
BWWBBWB	B	B	3	3
WWBBWBW	B	W	4	3

The minimum white count seen is 3.

Final answer:

3

Example 2

Input:

blocks = "WBWBBBW"
k = 2

Initial window:

"WB"

White count:

1

Slide the window.

Window	Outgoing	Incoming	White Count	Minimum
WB	-	-	1	1
BW	W	W	1	1
WB	B	B	1	1
BB	W	B	0	0
BB	B	B	0	0
BW	B	W	1	0

The minimum white count becomes 0.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most twice
Space	O(1)	Only a few integer variables are used

The sliding window moves through the string exactly once after initialization. Each step performs constant work, so the total runtime is linear in the size of the input string.

The algorithm does not allocate additional data structures proportional to the input size, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.minimumRecolors("WBBWWBBWBW", 7) == 3  # Provided example 1
assert solution.minimumRecolors("WBWBBBW", 2) == 0     # Provided example 2

assert solution.minimumRecolors("B", 1) == 0           # Single black block
assert solution.minimumRecolors("W", 1) == 1           # Single white block

assert solution.minimumRecolors("BBBBB", 3) == 0       # Already all black
assert solution.minimumRecolors("WWWWW", 3) == 3       # All white blocks

assert solution.minimumRecolors("BWBWBW", 1) == 0      # k = 1, black exists
assert solution.minimumRecolors("WWBWW", 1) == 0       # One black block satisfies requirement

assert solution.minimumRecolors("WWWWW", 5) == 5       # Entire string window, all white
assert solution.minimumRecolors("BBBBB", 5) == 0       # Entire string window, all black

assert solution.minimumRecolors("WBWBWBWB", 4) == 2    # Alternating pattern
assert solution.minimumRecolors("BBWWBB", 2) == 0      # Existing consecutive black blocks

assert solution.minimumRecolors("WWBBWW", 4) == 2      # Middle window optimal
assert solution.minimumRecolors("BWWWWW", 3) == 2      # Best window near beginning

Test	Why
"WBBWWBBWBW", 7	Verifies provided example
"WBWBBBW", 2	Verifies zero recolors case
"B", 1	Smallest valid input with black block
"W", 1	Smallest valid input with white block
"BBBBB", 3	Already satisfies condition
"WWWWW", 3	Requires recoloring every block in window
"BWBWBW", 1	Minimum window size
"WWBWW", 1	Single existing black block
"WWWWW", 5	Window equals full string, all white
"BBBBB", 5	Window equals full string, all black
"WBWBWBWB", 4	Alternating colors
"BBWWBB", 2	Multiple valid black windows
"WWBBWW", 4	Best window appears in middle
"BWWWWW", 3	Best window near boundary

Edge Cases

One important edge case occurs when k equals the length of the string. In this situation, the entire string becomes the only possible window. A buggy implementation might incorrectly attempt to slide beyond the valid range. The current solution handles this naturally because the sliding loop never executes when there are no additional windows.

Another important case is when the string already contains k consecutive black blocks. The correct answer should be 0, because no recoloring is necessary. The algorithm correctly detects this because a fully black window contains zero white blocks, making the minimum value zero.

A third important edge case is when every block is white. In this scenario, every position inside the chosen window must be recolored. The algorithm correctly counts all white blocks in each window, so the answer becomes exactly k.

A subtle case occurs when k == 1. Here, any single black block immediately satisfies the requirement. A naive implementation might overcomplicate the logic, but the sliding window still works perfectly because every window contains exactly one character. The algorithm simply finds whether any 'B' exists.