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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Recolors to Get K Consecutive Black Blocks

Number: 2463

Difficulty: Easy

Paid? No

Companies: DailyHunt

Problem Description

Given a string "blocks" consisting of characters 'W' and 'B' representing white and black blocks respectively, and an integer k, determine the minimum number of white blocks that need to be recolored to black so that there is at least one contiguous segment of k black blocks.

Key Insights

  • The goal is to find a sliding window of size k that will require the fewest recolor operations.
  • Count the number of white blocks ('W') in each window of size k; these represent the operations needed to convert that window to all black blocks.
  • As you slide the window over the string, update the count efficiently by subtracting the effect of the block that leaves the window and adding the effect of the new block.
  • The answer is the minimum count found across all the sliding windows.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we only perform a single pass over the string. Space Complexity: O(1), as we use only a few integer variables.

Solution

We use a sliding window approach with a fixed window size of k:

  1. Initialize the count of white blocks for the first window (from index 0 to k-1).
  2. Record this count as the minimum number of operations required.
  3. Slide the window one position at a time, updating the count by subtracting if the leftmost block is white and adding if the incoming block is white.
  4. Return the smallest count of whites in any window, which represents the minimal recolor operations required.

This approach efficiently identifies the optimal window while only traversing the string once.

Code Solutions

# Function to calculate minimum number of recolors needed.
def minimumRecolors(blocks: str, k: int) -> int:
    # Count white blocks in the first window of size k
    current_whites = blocks[:k].count('W')
    min_operations = current_whites
    
    # Slide the window across the string
    for i in range(1, len(blocks) - k + 1):
        # If the block that's leaving the window is white, decrement count.
        if blocks[i - 1] == 'W':
            current_whites -= 1
        # If the new block entering the window is white, increment count.
        if blocks[i + k - 1] == 'W':
            current_whites += 1
        # Update the minimum operations required.
        min_operations = min(min_operations, current_whites)
    
    return min_operations

# Example Usage:
print(minimumRecolors("WBBWWBBWBW", 7))  # Output: 3
print(minimumRecolors("WBWBBBW", 2))      # Output: 0
← Back to All Questions