Problem of The Day: Minimum Recolors to Get K Consecutive Black Blocks

Problem Statement

Intuition

The problem requires us to find the minimum number of recolors needed to get a contiguous substring of length k that consists only of black ('B') blocks. Our first thought is to consider all possible substrings of length k and determine how many white ('W') blocks need to be changed in each case.

Approach

We iterate through all possible substrings of length k in the given blocks string. For each substring, we count the number of 'W' characters and track the minimum count encountered.

Steps:

1. Iterate over all possible k-length substrings in blocks.
2. Count the number of 'W' blocks in each substring using Counter.
3. Keep track of the minimum number of white blocks found across all substrings.
4. Return this minimum value as the answer.

Complexity

• Time complexity:

  • We iterate through N - k + 1 substrings, and for each substring, we count the occurrences of 'W'. Using Counter(blocks[i:i+k]) takes O(k), making the overall complexity O(Nk).
  • This can be improved to O(N) using a sliding window approach.

• Space complexity:

  • We only use a few variables for tracking results and a Counter object with at most O(k) space, leading to an overall O(1) auxiliary space complexity.

Code

from collections import Counter

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        N = len(blocks)
        res = float('inf')
        for i in range(N - k + 1):
            counter = Counter(blocks[i:i+k])
            res = min(res, counter['W'])
        return res

Editorial

Approach 1: Queue

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

        # Initiate queue with first k values
        for i in range(k):
            current_char = blocks[i]
            if current_char == "W":
                num_whites += 1
            block_queue.append(current_char)

        # Set initial minimum
        num_recolors = num_whites

        for i in range(k, len(blocks)):

            # Remove front element from queue and update current number of white blocks
            if block_queue.popleft() == "W":
                num_whites -= 1

            # Add current element to queue and update current number of white blocks
            current_char = blocks[i]
            if current_char == "W":
                num_whites += 1
            block_queue.append(current_char)

            # Update minimum
            num_recolors = min(num_recolors, num_whites)

        return num_recolors

Approach 2: Sliding Window

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        left = 0
        num_whites = 0
        num_recolors = float("inf")

        # Move right pointer
        for right in range(len(blocks)):

            # Increment num_whites if block at right pointer is white
            if blocks[right] == "W":
                num_whites += 1

            # k consecutive elements are found
            if right - left + 1 == k:

                # Update minimum
                num_recolors = min(num_recolors, num_whites)

                # Decrement num_whites if block at left pointer is white
                if blocks[left] == "W":
                    num_whites -= 1

                # Move left pointer
                left += 1

        return num_recolors