Watch 10 video solutions for Minimum Recolors to Get K Consecutive Black Blocks, a easy level problem involving String, Sliding Window. This walkthrough by NeetCodeIO has 7,220 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |