We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Recolors to Get K Consecutive Black Blocks

Difficulty: Easy

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

Key Insights

  • The problem can be viewed as a sliding window problem where we check each segment of size k in the string.
  • We need to count the number of white blocks in each window of size k, as these are the blocks that need to be recolored to achieve the desired consecutive black blocks.
  • By sliding the window across the string, we can efficiently calculate the number of recolors needed for each segment.
  • The minimum recolors found across all segments will be our answer.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we utilize a sliding window approach. We maintain a window of size k and count the number of white blocks ('W') within this window. As we slide the window from the start of the string to the end, we update our count based on the blocks that enter or leave the window. The goal is to find the minimum count of white blocks in any of the windows, which represents the minimum number of recolors needed.

Code Solutions

def minimumRecolors(blocks: str, k: int) -> int:
    n = len(blocks)
    min_recolors = float('inf')
    current_recolors = 0

    # Count the number of 'W's in the first window of size k
    for i in range(k):
        if blocks[i] == 'W':
            current_recolors += 1
    
    min_recolors = current_recolors

    # Slide the window across the string
    for i in range(k, n):
        # Remove the block going out of the window
        if blocks[i - k] == 'W':
            current_recolors -= 1
        # Add the new block coming into the window
        if blocks[i] == 'W':
            current_recolors += 1
            
        # Update the minimum recolors found
        min_recolors = min(min_recolors, current_recolors)

    return min_recolors
← Back to All Questions