algoadvance

Leetcode 2379. Minimum Recolors to Get K Consecutive Black Blocks

Problem Statement

You are given a string blocks consisting of the characters ‘W’ and ‘B’, which represent white and black blocks respectively. You are also given an integer k, representing the desired number of consecutive black blocks. Your goal is to find the minimum number of recolors needed to get at least one string of k consecutive black blocks.

Strategy

To achieve the goal, we can use a sliding window technique:

  1. Traverse the string blocks with a window of size k.
  2. For each window, count the number of white blocks (‘W’).
  3. Track the minimum count of white blocks among all windows. This count represents the minimum number of recolors needed.

Clarifying Questions

  1. Can the string blocks contain characters other than ‘W’ or ‘B’?
    • Assumption: No, it only contains ‘W’ and ‘B’.
  2. Is the length of blocks always greater than or equal to k?
    • Assumption: Yes, otherwise the problem would not be valid as we cannot have k consecutive blocks.
  3. Are there any constraints on the values of k?
    • Assumption: k is a positive integer no greater than the length of blocks.

Code

Here is the code implementation based on the sliding window technique:

public class MinimumRecolors {
    public int minimumRecolors(String blocks, int k) {
        int n = blocks.length();
        int minRecolors = Integer.MAX_VALUE;
        int currentWhites = 0;
        
        // Calculate whites in the first window
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') {
                currentWhites++;
            }
        }
        minRecolors = currentWhites;
        
        // Slide the window from start to end
        for (int i = k; i < n; i++) {
            // Remove the influence of the (i-k)th element
            if (blocks.charAt(i - k) == 'W') {
                currentWhites--;
            }
            // Add the influence of the ith element
            if (blocks.charAt(i) == 'W') {
                currentWhites++;
            }
            // Update minimum recolors
            minRecolors = Math.min(minRecolors, currentWhites);
        }
        
        return minRecolors;
    }

    // To run and test the solution
    public static void main(String[] args) {
        MinimumRecolors obj = new MinimumRecolors();
        String blocks = "WBWBBBW";
        int k = 3;
        System.out.println(obj.minimumRecolors(blocks, k)); // Output: 1
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string blocks. This is because we are traversing the string once to compute the number of whites in the sliding window, and another traversal to update the sliding window while maintaining the count. The space complexity is O(1) since we are using a constant amount of extra space.

If you have any further questions or need clarifications, feel free to ask!

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