Leetcode 2379: Minimum Recolors to Get K Consecutive Black Blocks

Input: The input consists of a string `blocks` of length `n`, containing characters 'W' and 'B'. You are also given an integer `k` which is the desired number of consecutive black blocks.

Example: blocks = 'BBWWBWBW', k = 4

Constraints:

• 1 <= blocks.length <= 100

• blocks[i] is either 'W' or 'B'.

• 1 <= k <= blocks.length

Output: Return the minimum number of operations needed to ensure there is at least one occurrence of `k` consecutive black blocks.

Example: Output: 2

Constraints:

Goal: The goal is to find the minimum number of operations required to change some white blocks to black in order to have at least one sequence of `k` consecutive black blocks.

Steps:

• 1. Traverse through the string `blocks` and count the number of black blocks in each sliding window of length `k`.

• 2. For each window, calculate the number of white blocks (W) and track the minimum number of changes required.

• 3. Return the minimum number of recoloring operations.

Goal: The string `blocks` will always contain at least one character and the value of `k` will always be less than or equal to the length of the string.

Steps:

• The length of `blocks` will be between 1 and 100.

• The value of `k` will be between 1 and the length of `blocks`.

Assumptions:

• The input string `blocks` will consist only of the characters 'W' and 'B'.

• The integer `k` is valid and will not exceed the length of the input string.

• Input: Input: blocks = 'BBWWBWBW', k = 4

• Explanation: Here, the desired sequence is 4 consecutive black blocks. The minimum number of operations required to achieve this is 2, as we can change the 3rd and 6th blocks to 'B'.

• Input: Input: blocks = 'WBBWWBB', k = 3

• Explanation: In this case, the sequence already contains 3 consecutive black blocks, so no operations are needed. The result is 0.

Approach: To solve this problem efficiently, we can use a sliding window technique to calculate the number of black blocks in each window of size `k`. For each window, we count the number of white blocks and track the minimum count across all possible windows.

Observations:

• The problem asks for the minimum recoloring operations, so we should focus on finding the windows with the most black blocks already present.

• By using a sliding window of size `k`, we can efficiently calculate the number of black blocks in each segment and determine the minimum changes required.

Steps:

• 1. Initialize a sliding window of size `k` and traverse the string `blocks`.

• 2. Count the number of black blocks in the current window.

• 3. Calculate how many white blocks need to be recolored to black in each window.

• 4. Track the minimum number of recoloring operations across all windows and return this value.

Empty Inputs:

• The input string `blocks` will never be empty.

Large Inputs:

• The input string can be as large as 100 characters, so the algorithm should handle this efficiently.

Special Values:

• If the string already contains `k` consecutive black blocks, no operations are needed.

Constraints:

• Ensure that `k` is always less than or equal to the length of the input string.

int minimumRecolors(string blocks, int k) {
int b = 0, mb = 0;
for (int i = 0; i < blocks.size(); ++i) {
    b += blocks[i] == 'B';
    if (i >= k)
        b -= blocks[i - k] == 'B';
    mb = max(b, mb);
}
return k - mb;
}

1 : Function Definition

int minimumRecolors(string blocks, int k) {

Defines the function `minimumRecolors` that accepts a string `blocks` representing a sequence of 'B' and 'W' and an integer `k` representing the length of the window. The function returns the minimum number of recolors needed in any substring of length `k` to make it all 'B'.

2 : Variable Initialization

int b = 0, mb = 0;

Initializes two integer variables: `b` to count the number of 'B's in the current window, and `mb` to store the maximum number of 'B's in any valid window of size `k` encountered so far.

3 : Loop Start

for (int i = 0; i < blocks.size(); ++i) {

Starts a for loop to iterate over each character in the string `blocks`. This loop will examine each position to update the count of 'B's in the current window.

4 : Count 'B's

    b += blocks[i] == 'B';

Increments the counter `b` each time a 'B' is encountered at the current position `i`.

5 : Window Size Check

    if (i >= k)

Checks if the current index `i` has reached or exceeded the window size `k`. This is to ensure that the sliding window approach begins to remove elements as it moves forward.

6 : Adjust Window

        b -= blocks[i - k] == 'B';

If the window has moved past `k`, subtracts the count of 'B' at the position `i - k` (the element that is no longer in the window).

7 : Update Max 'B' Count

    mb = max(b, mb);

Updates the maximum count of 'B's found in any window of size `k` so far by comparing the current count `b` with `mb`.

8 : Return Result

return k - mb;

Returns the minimum number of recolors required by subtracting the maximum number of 'B's found in any valid window (`mb`) from the total window size `k`. The result represents the number of 'W's that need to be recolored to 'B'.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) as we only pass through the string once, adjusting the sliding window as we go.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only need a fixed amount of space for counting and the sliding window.

Leetcode 2379: Minimum Recolors to Get K Consecutive Black Blocks

Explore →