2379. Minimum Recolors to Get K Consecutive Black Blocks
Problem Description
In this problem, we have a string blocks
composed of characters 'W'
and 'B'
, which represent white and black blocks, respectively. This string is indexed starting at 0, meaning the first element is at index 0. Our objective is to find the minimum number of operations required to ensure that there is at least one segment in the string consisting of k
consecutive black blocks. An operation consists of changing a white block into a black block.
Imagine we have a block arrangement like "WBWBBW" and we want at least 3 consecutive black blocks. We need to determine the fewest changes needed to reach that goal; in this case, it's 1 operation by changing the second block from white to black resulting in "WBBWBB".
The problem specifies two key elements central to our task:
- We need to count the number of operations, which correlates to the number of white blocks (
'W'
) that we need to recolor into black blocks ('B'
). - We are seeking to create a continuous segment of
k
consecutive black blocks.
Intuition
To arrive at the solution, we need to consider a sliding window approach. The reason a sliding window works well here is that we're interested in a continuous sequence of blocks — specifically, subsequences of length k
. As we slide the window across the string, we'll look at the number of white blocks within each window, because those are our candidates for recoloring.
Initial thought might involve checking every possible window of k
blocks in the string, and for each window, counting the number of white blocks and keeping track of the minimum count seen. But this is inefficient because we would be doing repetitive counting. A more optimized approach involves only doing the counting once and then updating the count as the window slides.
The solution code implements this efficient approach:
- First, it counts the number of white blocks within the first
k
blocks. This is our initial answer — the worst-case number of operations, if the firstk
blocks contain the most white blocks. - Then, the algorithm enters a loop where it slides the window one block at a time to the right. As the window slides, it adjusts the count by adding one if a white block enters the window on the right, and subtracting one if a white block leaves the window on the left.
- After each adjustment, it updates the answer with the new count if it's lower than the previous answer.
This allows us to go through the entire blocks
string only once (after the initial count), adjusting the white block count and minimum number as we slide the window. The result is the minimum number of operations needed to ensure a sequence of k
black blocks.
Learn more about Sliding Window patterns.
Solution Approach
The implementation of this solution uses a simple but effective pattern known as the sliding window technique. Here's a step-by-step walkthrough of the algorithm, as implemented in the provided solution code:
-
Initialize an integer variable
ans
(short for answer) to hold the minimum number of recoloring operations needed and another variablecnt
(short for count) to keep track of the number of white blocks within the current window. Calculate the number of white blocks in the first window of sizek
using thecount
method on the substringblocks[:k]
. Setans
to this initial count. -
Use a loop to iterate through the string
blocks
, starting from thek
th index up to the end of the string (not inclusive). This loop shifts the fixed-size window one block to the right with each iteration. -
As the window slides, update
cnt
:- Increment
cnt
by 1 if the new block coming into the right side of the window is a white block (blocks[i] == 'W'
). - Decrement
cnt
by 1 if the block that is sliding out of the left side of the window is a white block (blocks[i - k] == 'W'
).
- Increment
-
After updating
cnt
, compare it with the current value ofans
. Ifcnt
is smaller (which means the window now contains fewer white blocks than any window seen before), updateans
tocnt
. -
After the loop has iterated over the whole string,
ans
holds the minimum number of operations required. Returnans
.
No complex data structures are needed for this approach; only integer counters are used. The algorithm runs in linear time, O(n), where n is the length of the blocks
string. It only requires a constant amount of additional space, resulting in O(1) space complexity.
By maintaining the count cnt
as the window slides over the string, the solution avoids the need to recount white blocks in each new window. This is much more efficient than a naive approach where you might recount white blocks for every new window of size k
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a smaller example. Consider the string blocks = "WWBWB"
and let's say we want at least k = 3
consecutive black blocks.
Following the steps outlined in the solution approach:
-
Initialize variables and count white blocks in the first window: The variable
ans
is set to the number of white blocks in the first window of size 3, which isblocks[:3] = "WWB"
. This has 2 white blocks, soans = 2
. We also initialize the count variablecnt = 2
. -
Iterate through
blocks
with a sliding window: We start our loop from index3
, which is the fourth block inblocks
, and go up to the end of the string. -
Update count and answer:
- At index
3
, the block is'W'
, so no new black block is added to the window. Since we're not adding a white block on the right,cnt
remains2
. - However, we should also slide the window, which means we remove the leftmost block from our initial count. The leftmost block within our initial window is white (
blocks[0] = 'W'
), which means we need to decrementcnt
by 1. Now,cnt = 1
.
Therefore, after the first iteration, the window looks at
"WBW"
, withcnt = 1
. - At index
-
Update the answer: Our new
cnt
is less than the previousans
, so we setans
tocnt
. Now,ans = 1
. -
Final return value: In the next and final iteration, the window would look at
"BWB"
, and since there's 1 white block entering the window on the right (blocks[4] == 'W'
),cnt
is incremented back to2
. However, the block that leaves on the left (blocks[1]
) is a black block, socnt
remains2
. There's no need to updateans
sincecnt
is not smaller thanans
.
Following this process, we've completed our sweep of the block string, and ans
holds the value 1
, which represents the minimum number of operations required to ensure there is a segment of 3
consecutive black blocks in the string.
Thus, the output would be 1
because we need to change one white block to achieve a segment of 3
consecutive black blocks ("WWBWB"
would become "WWBBB"
).
Solution Implementation
1class Solution:
2 def minimumRecolors(self, blocks: str, k: int) -> int:
3 # Initial count of 'W' in the first window of size k
4 white_count = blocks[:k].count('W')
5 # Initialize minimum white blocks to be recolored with the count from the first window
6 min_recolors = white_count
7
8 # Slide the window of size k through the blocks string
9 for index in range(k, len(blocks)):
10 # If the newly included block in the window is white, increment the count
11 if blocks[index] == 'W':
12 white_count += 1
13 # If the block that is exiting the window is white, decrement the count
14 if blocks[index - k] == 'W':
15 white_count -= 1
16 # Update the minimum if the current count is less than the previous minimum
17 min_recolors = min(min_recolors, white_count)
18
19 # Return the minimum number of white blocks that need to be recolored
20 return min_recolors
21
1class Solution {
2 // Method to find the minimum number of recolors needed to get at least k consecutive black blocks
3 public int minimumRecolors(String blocks, int k) {
4 // Initialize the count of white blocks within the first window of size k
5 int whiteCount = 0;
6 for (int i = 0; i < k; ++i) {
7 if (blocks.charAt(i) == 'W') {
8 whiteCount++;
9 }
10 }
11
12 // Initialize the answer with the count of white blocks within the first window
13 int minRecolors = whiteCount;
14
15 // Slide the window of size k across the string and update the minimum recolors requird
16 for (int i = k; i < blocks.length(); ++i) {
17 // If the entering character is white, increment white count
18 if (blocks.charAt(i) == 'W') {
19 whiteCount++;
20 }
21 // If the exiting character is white, decrement white count
22 if (blocks.charAt(i - k) == 'W') {
23 whiteCount--;
24 }
25 // Update the minimum recolors if the current count is less than the previous minimum
26 minRecolors = Math.min(minRecolors, whiteCount);
27 }
28
29 // Return the minimum number of recolors required
30 return minRecolors;
31 }
32}
33
1class Solution {
2public:
3 // Function to find the minimum number of recolors needed
4 // to get at least 'k' consecutive black blocks
5 int minimumRecolors(string blocks, int k) {
6 // Count the number of white blocks in the first 'k' block segment
7 int whiteBlockCount = count(blocks.begin(), blocks.begin() + k, 'W');
8
9 // The minimum recolors needed is initially set to the number
10 // of white blocks in the first window of size 'k'
11 int minRecolors = whiteBlockCount;
12
13 // Iterate over the blocks starting from the 'k'th block
14 for (int i = k; i < blocks.size(); ++i) {
15 // Increase whiteBlockCount if the current block is white
16 whiteBlockCount += blocks[i] == 'W';
17
18 // Decrease whiteBlockCount if the leftmost block of
19 // the previous window was white
20 whiteBlockCount -= blocks[i - k] == 'W';
21
22 // Update minRecolors to the smallest number of white blocks
23 // seen in any window of size 'k'
24 minRecolors = min(minRecolors, whiteBlockCount);
25 }
26
27 // Return the minimum number of recolors needed
28 return minRecolors;
29 }
30};
31
1// Function to find the minimum number of recolors to get at least k consecutive black blocks.
2// @param blocks - String representing the arrangement of black (B) and white (W) blocks.
3// @param k - Number representing the desired consecutive black blocks length.
4// @returns The minimum number of recolors required (changing 'W' to 'B').
5function minimumRecolors(blocks: string, k: number): number {
6
7 // Initialize a counter for white blocks in the first window of size k.
8 let whiteCount = 0;
9 for (let i = 0; i < k; ++i) {
10 whiteCount += blocks[i] === 'W' ? 1 : 0;
11 }
12
13 // The answer starts off as the number of white blocks in the first window.
14 let minRecolors = whiteCount;
15
16 // Slide the window of size k across the blocks string while updating the count.
17 for (let i = k; i < blocks.length; ++i) {
18 // If the new block is white, increase the count.
19 whiteCount += blocks[i] === 'W' ? 1 : 0;
20 // If the block exiting the window is white, decrease the count.
21 whiteCount -= blocks[i - k] === 'W' ? 1 : 0;
22 // Update the answer with the minimum count seen so far.
23 minRecolors = Math.min(minRecolors, whiteCount);
24 }
25
26 // Return the minimum number of recolors needed.
27 return minRecolors;
28}
29
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed based on the operations performed within the loop. The loop runs from k
to len(blocks)
, which indicates that the loop runs len(blocks) - k
times. Within each iteration, the code performs constant-time operations such as comparison and increment/decrement operations. Therefore, the overall time complexity is O(len(blocks) - k)
, which simplifies to O(n)
where n
is the length of the blocks
string.
Space Complexity
The space complexity is determined by the amount of additional space used by the algorithm relative to the input size. The given code uses a fixed number of variables (ans
, cnt
, i
) that do not depend on the size of the input. Therefore, the space complexity remains constant, regardless of the input size. Consequently, the space complexity of the code is O(1)
, indicating constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.