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 <= nProblem 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.
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.
Time Complexity: O(n), Space Complexity: O(1)
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.
Time Complexity: O(n), Space Complexity: O(n)
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).
| 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 | — |
| 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 |
Minimum Recolors to Get K Consecutive Black Blocks - Leetcode 2379 • NeetCodeIO • 7,220 views views
Watch 9 more video solutions →Practice Minimum Recolors to Get K Consecutive Black Blocks with our built-in code editor and test cases.
Practice on FleetCode