Minimum Recolors to Get K Consecutive Black Blocks - Solution & Explanation
Problem Statement
You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the ith block. The characters 'W' and 'B' denote the colors white and black, respectively.
You are also given an integer k, which is the desired number of consecutive black blocks.
In one operation, you can recolor a white block such that it becomes a black block.
Return the minimum number of operations needed such that there is at least one occurrence of k consecutive black blocks.
Example 1:
Input: blocks = "WBBWWBBWBW", k = 7 Output: 3 Explanation: One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks so that blocks = "BBBBBBBWBW". It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations. Therefore, we return 3.
Example 2:
Input: blocks = "WBWBBBW", k = 2 Output: 0 Explanation: No changes need to be made, since 2 consecutive black blocks already exist. Therefore, we return 0.
Constraints:
n == blocks.length1 <= n <= 100blocks[i]is either'W'or'B'.1 <= k <= n
Approach Overview
Problem Overview: You are given a string of blocks where 'B' represents a black block and 'W' represents a white block. The goal is to determine the minimum number of recolors needed so that at least k consecutive blocks become black. Recoloring means turning a white block into a black one.
Approach 1: Sliding Window (O(n) time, O(1) space)
The optimal strategy uses a fixed-size sliding window of length k. Every window represents a candidate segment that could become k consecutive black blocks. Instead of counting black blocks, count how many 'W' characters appear inside the window because each white block requires one recolor.
Start by counting whites in the first window of size k. Then slide the window one step at a time: remove the effect of the outgoing character and add the incoming one. Track the minimum number of whites seen in any window. That value is the minimum recolors required.
This approach works because every valid solution must correspond to some contiguous segment of length k. Sliding window avoids recomputing counts from scratch and updates the result in constant time per step. The algorithm runs in O(n) time with O(1) extra space, making it ideal for interview settings. Problems involving fixed-size subarrays frequently use the sliding window technique on top of basic string traversal.
Approach 2: Prefix Sum with Optimization (O(n) time, O(n) space)
Another method uses a prefix sum array to track how many white blocks appear up to each index. Construct an array where prefix[i] stores the number of 'W' characters from the start of the string through index i. Once built, the number of whites inside any window [l, r] can be computed in constant time using prefix[r] - prefix[l-1].
Iterate through all possible windows of length k. For each window, compute the number of white blocks using the prefix sum and update the minimum recolor count. This avoids repeatedly scanning each segment and keeps the runtime linear.
The prefix sum approach is slightly heavier in memory but useful when the problem later evolves to support multiple queries or variable window ranges. It demonstrates a common pattern where cumulative counts allow constant-time range queries. This pattern appears frequently in prefix sum problems.
Recommended for interviews: Interviewers typically expect the sliding window approach. It shows you recognize that the window size is fixed and can maintain counts incrementally. The prefix sum method also achieves O(n) time, but the sliding window version is simpler, uses constant space, and demonstrates stronger pattern recognition.
Approach 1: Sliding Window Approach
The Sliding Window Approach keeps track of a dynamic set of elements (window) and updates the count of 'W' blocks for each position of the window. It enables the solution to efficiently calculate the minimum number of recolors needed for k consecutive 'B' blocks.
The C solution uses a sliding window of size k over the string 'blocks'. It first sets up an initial count of white blocks ('W') in the first window. As the window slides, for each new block entering the window and for each old block leaving, it adjusts the count of white blocks. The solution tracks the minimum count of 'W' found in any window.
Complexity
Time Complexity: O(n), Space Complexity: O(1)
Approach 2: Prefix Sum with Optimization
The Prefix Sum with Optimization approach calculates the number of 'W' blocks in each possible window using precomputed cumulative sums. By calculating differences between prefix sums at appropriate indices, it allows for efficient queries of any window, achieving the solution in linear time.
This C solution calculates a prefix sum of white blocks ('W') to allow for quick query over any subsequence of the array. The prefix sums help in efficiently calculating the number of 'W' blocks in a given window.
Complexity
Time Complexity: O(n), Space Complexity: O(n)
Approach 3: Sliding Window
We observe that what the problem actually asks for is the minimum number of white blocks in a sliding window of size k.
Therefore, we only need to traverse the string blocks, use a variable cnt to count the number of white blocks in the current window, and then use a variable ans to maintain the minimum value.
After the traversal ends, we can get the answer.
The time complexity is O(n), where n is the length of the string blocks. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), Space Complexity: O(1) |
| Prefix Sum with Optimization | Time Complexity: O(n), Space Complexity: O(n) |
| Sliding Window | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution when scanning fixed-size windows in strings or arrays |
| Prefix Sum with Optimization | O(n) | O(n) | Useful when multiple range queries or dynamic window checks are required |
Video Solution
Minimum Recolors to Get K Consecutive Black Blocks - Leetcode 2379 • NeetCodeIO • 7,609 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Recolors to Get K Consecutive Black Blocks easy or hard?
Minimum Recolors to Get K Consecutive Black Blocks Python/Java solution
How to solve Minimum Recolors to Get K Consecutive Black Blocks in O(n)?
What is the best approach for Minimum Recolors to Get K Consecutive Black Blocks?
Is Minimum Recolors to Get K Consecutive Black Blocks asked at Google/Amazon/Meta?
What data structure is used in Minimum Recolors to Get K Consecutive Black Blocks?
What is the time complexity of Minimum Recolors to Get K Consecutive Black Blocks?
Ready to solve this problem?
Practice Minimum Recolors to Get K Consecutive Black Blocks with our built-in code editor and test cases.
Practice on FleetCode