algoadvance

Leetcode 2379. Minimum Recolors to Get K Consecutive Black Blocks

Problem Statement

You are given a string blocks representing a row of blocks where each block can be either ‘W’ (white) or ‘B’ (black). You are also given an integer k, the number of consecutive blocks you need to get. You need to find the minimum number of recolors needed to get at least k consecutive black blocks.

Example:

Clarifying Questions

  1. Can the input blocks string be empty?
    • No, the constraints guarantee that the length of the string is at least 1.
  2. What is the maximum length of the string blocks?
    • The maximum length is not explicitly specified but we should assume it can be quite large.
  3. Are there any characters other than ‘W’ and ‘B’ in the input string?
    • No, the string blocks will only contain ‘W’ and ‘B’.

Strategy

  1. Sliding Window Technique:
    • Use a sliding window of size k to iterate through the string.
    • For each window, count the number of ‘W’ blocks (i.e., white blocks).
    • Track the minimum number of ‘W’ blocks found in any window of size k.
  2. Calculate Initial Window:
    • Begin by counting the ‘W’ blocks in the first window of size k.
  3. Slide the Window:
    • Move the window one block to the right.
    • Adjust the count of ‘W’ blocks by subtracting the block that is no longer in the window and adding the new block that enters the window.
    • Update the minimum white block count if the current window has fewer ‘W’ blocks.
  4. Return the Minimum:
    • The minimum number of ‘W’ blocks in any window of size k is the answer, as these are the blocks that need to be recolored.

Time Complexity

Code

Here’s the C++ implementation of the solution:

#include <string>
#include <algorithm>

class Solution {
public:
    int minimumRecolors(std::string blocks, int k) {
        int n = blocks.size();
        
        // Initial count of 'W' in the first window of size k
        int whiteCount = 0;
        for (int i = 0; i < k; ++i) {
            if (blocks[i] == 'W') {
                ++whiteCount;
            }
        }
        
        int minRecolors = whiteCount;
        
        // Sliding window approach
        for (int i = k; i < n; ++i) {
            // Remove the effect of the leftmost block of the previous window
            if (blocks[i - k] == 'W') {
                --whiteCount;
            }
            // Add the effect of the current block
            if (blocks[i] == 'W') {
                ++whiteCount;
            }
            // Update minimum recolors needed
            minRecolors = std::min(minRecolors, whiteCount);
        }
        
        return minRecolors;
    }
};

By following this approach, you can efficiently find the minimum number of blocks that need to be recolored to get at least k consecutive black blocks.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI