algoadvance

You are given a string blocks of length n where each character is either ‘W’ or ‘B’, representing white or black blocks respectively. You are also given an integer k, the number of consecutive black blocks you want. The task is to determine the minimum number of recolors needed to get at least k consecutive black blocks.

Clarifying Questions

1. Input Constraints:
   • 1 <= k <= n <= 100
   • blocks[i] is either ‘W’ or ‘B’
2. Output:
   • Return the minimum number of recolors needed to get k consecutive ‘B’ blocks.

Strategy

1. Sliding Window Approach:
   • Use a sliding window of size k to traverse through the blocks string.
   • Count the number of white blocks (‘W’) within the sliding window.
   • As we slide the window from the start of the string to the end, update the count based on the new character added to the window and the character removed from it.
   • Track the minimum number of white blocks for any window position, since each white block in the window represents a recolor required to obtain k consecutive black blocks.
2. Initialization:
   • Start with the first window (the first k characters) and count the number of ‘W’ blocks.
   • Slide the window across the string, updating the count of ‘W’ based on the characters entering and leaving the window.
3. Final Result:
   • The minimum number of white blocks counted in any window during the slide represents the minimum number of recolors needed.

Code

def minimumRecolors(blocks: str, k: int) -> int:
    # Initialize the minimum recolors to a large number.
    min_recolors = float('inf')
    
    # Count the number of 'W' in the initial window of size k.
    current_recolors = blocks[:k].count('W')
    
    # Initialize min_recolors with the first window's count of 'W'
    min_recolors = min(min_recolors, current_recolors)
    
    # Slide the window across the string, updating counts.
    for i in range(1, len(blocks) - k + 1):
        # Check the character that is leaving the window
        if blocks[i - 1] == 'W':
            current_recolors -= 1
        # Check the character that is entering the window
        if blocks[i + k - 1] == 'W':
            current_recolors += 1
        # Update the minimum recolors needed
        min_recolors = min(min_recolors, current_recolors)
    
    return min_recolors

Time Complexity

• Initialization: Counting the ‘W’ in the first window takes O(k).
• Sliding Window: Each update of the window and minimum recolors calculation takes constant time O(1).
• Total: The sliding window moves through the entire length of the string (n-k+1 positions), making the overall time complexity O(n).

This approach efficiently finds the minimum recolors required to achieve at least k consecutive ‘B’ blocks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?