Minimum Recolors to Get K Consecutive Black Blocks

We need to track the consecutive black blocks and find the minimum number of white blocks to be recolored within a window of size k to achieve the desired k consecutive black blocks.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        # Start by finding the number of black blocks in the first window of size k
        black_count = sum(1 for i in range(k) if blocks[i] == 'B')

        # Calculate the initial number of operations needed by subtracting the black count from k
        min_operations = k - black_count

        # Iterate through the blocks starting from k, maintaining a window of size k
        for i in range(k, len(blocks)):
            # If the block exiting the window was black, decrement the black count
            if blocks[i - k] == 'B':
                black_count -= 1

            # If the block entering the window is black, increment the black count
            if blocks[i] == 'B':
                black_count += 1

            # Calculate the number of operations needed for the current window
            operations_needed = k - black_count

            # Update the minimum number of operations if the current operations needed is smaller
            if operations_needed < min_operations:
                min_operations = operations_needed

        # Return the minimum number of operations
        return min_operations

Explanation

We maintain a window of size k, initially starting from the first k blocks.
Inside the window, we track the consecutive black blocks, and we calculate the number of white blocks that need to be recolored to achieve k consecutive black blocks.
As we iterate through the blocks, we update the black count for the sliding window and keep track of the minimum operations needed.
Finally, we return the minimum number of operations required to achieve the desired k consecutive black blocks.