Minimum Recolors to Get K Consecutive Black Blocks solution and explanation
Google
9 more videos on this problem
Minimum Recolors to Get K Consecutive Black Blocks - Leetcode 2379NeetCodeIO · 7:46 · 7K views
Minimum Recolors to Get K Consecutive Black Blocks | 2 Approaches | Leetcode 2379 | codestorywithMIKcodestorywithMIK · 19:14 · 5K views
Minimum Recolors to Get K Consecutive Black Blocks | Leetcode 2379Techdose · 10:27 · 2K views
2379. Minimum Recolors to Get K Consecutive Black Blocks | LeetCode Daily Challenge | FAANGShashCode · 10:30 · 2K views
2379. Minimum Recolors to Get K Consecutive Black Blocks (Leetcode Easy)Programming Live with Larry · 4:25 · 1K views
Leetcode | 2379. Minimum Recolors to Get K Consecutive Black Blocks | Easy | Java SolutionDeveloper Docs · 7:29 · 1K views
2379. Minimum Recolors to Get K Consecutive Black Blocks | Sliding WindowAryan Mittal · 12:49 · 1K views
8. Minimum Recolors to Get K Consecutive Black Blocks | Fixed Sliding window - Medium| Leetcode 2379Ayushi Sharma · 6:26 · 340 views
Leetcode 2379. Minimum Recolors to Get K consecutive black blocks | Sliding windowJeezy Leets · 6:29 · 214 views
LeetCode 2379 Minimum Recolors to Get K Consecutive Black Blocks | Fixed Sliding Window | GoogleCode Harmony · 14:33 · 153 views
The problem
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.
def min_recolors(blocks, k):
min_w = k
current_w = 0
# Initial window
for i in range(k):
if blocks[i] == 'W':
current_w += 1
min_w = current_w
# Sliding the window
for i in range(k, len(blocks)):
if blocks[i-k] == 'W':
current_w -= 1
if blocks[i] == 'W':
current_w += 1
min_w = min(min_w, current_w)
return min_w
print(min_recolors("WBBWWBBWBW", 7))public class MinRecolors {
public static int minRecolors(String blocks, int k) {
int n = blocks.length();
int minW = k;
int currentW = 0;
// Initial window
for (int i = 0; i < k; i++) {
if (blocks.charAt(i) == 'W')
currentW++;
}
minW = currentW;
// Sliding the window
for (int i = k; i < n; i++) {
if (blocks.charAt(i-k) == 'W')
currentW--;
if (blocks.charAt(i) == 'W')
currentW++;
if (currentW < minW)
minW = currentW;
}
return minW;
}
public static void main(String[] args) {
String blocks = "WBBWWBBWBW";
int k = 7;
System.out.println(minRecolors(blocks, k));
}
}#include <iostream>
#include <string>
int minRecolors(std::string blocks, int k) {
int n = blocks.size();
int minW = k;
int currentW = 0;
// Initial window
for (int i = 0; i < k; i++) {
if (blocks[i] == 'W')
currentW++;
}
minW = currentW;
// Sliding the window
for (int i = k; i < n; i++) {
if (blocks[i-k] == 'W')
currentW--;
if (blocks[i] == 'W')
currentW++;
if (currentW < minW)
minW = currentW;
}
return minW;
}
int main() {
std::string blocks = "WBBWWBBWBW";
int k = 7;
std::cout << minRecolors(blocks, k) << std::endl;
return 0;
}function minRecolors(blocks, k) {
let n = blocks.length;
let minW = k;
let currentW = 0;
// Initial window
for (let i = 0; i < k; i++) {
if (blocks[i] === 'W')
currentW++;
}
minW = currentW;
// Sliding the window
for (let i = k; i < n; i++) {
if (blocks[i-k] === 'W')
currentW--;
if (blocks[i] === 'W')
currentW++;
minW = Math.min(minW, currentW);
}
return minW;
}
console.log(minRecolors('WBBWWBBWBW', 7));#include <stdio.h>
#include <string.h>
int minRecolors(char *blocks, int k) {
int n = strlen(blocks);
int minW = k;
int currentW = 0;
// Initial window
for (int i = 0; i < k; i++) {
if (blocks[i] == 'W')
currentW++;
}
minW = currentW;
// Sliding the window
for (int i = k; i < n; i++) {
if (blocks[i-k] == 'W')
currentW--;
if (blocks[i] == 'W')
currentW++;
if (currentW < minW)
minW = currentW;
}
return minW;
}
int main() {
char blocks[] = "WBBWWBBWBW";
int k = 7;
printf("%d\n", minRecolors(blocks, k));
return 0;
}using System;
class Program {
static int MinRecolors(string blocks, int k) {
int n = blocks.Length;
int minW = k;
int currentW = 0;
for (int i = 0; i < k; i++) {
if (blocks[i] == 'W')
currentW++;
}
minW = currentW;
for (int i = k; i < n; i++) {
if (blocks[i-k] == 'W')
currentW--;
if (blocks[i] == 'W')
currentW++;
if (currentW < minW)
minW = currentW;
}
return minW;
}
static void Main() {
Console.WriteLine(MinRecolors("WBBWWBBWBW", 7));
}
}The Python version applies a sliding window mechanism to determine the minimum recolors necessary. It efficiently maintains the count of white blocks with each shift of the window, ensuring computational efficiency.
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.
def min_recolors(blocks, k):
n = len(blocks)
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i-1] + (1 if blocks[i-1] == 'W' else 0)
min_w = n
for i in range(k, n + 1):
min_w = min(min_w, prefix_sum[i] - prefix_sum[i-k])
return min_w
print(min_recolors("WBBWWBBWBW", 7))public class MinRecolorsWithPrefixSum {
public static int minRecolors(String blocks, int k) {
int n = blocks.length();
int[] prefixSum = new int[n+1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i-1] + (blocks.charAt(i-1) == 'W' ? 1 : 0);
}
int minW = n;
for (int i = k; i <= n; i++) {
minW = Math.min(minW, prefixSum[i] - prefixSum[i-k]);
}
return minW;
}
public static void main(String[] args) {
System.out.println(minRecolors("WBBWWBBWBW", 7));
}
}#include <iostream>
#include <vector>
using namespace std;
int minRecolors(string blocks, int k) {
int n = blocks.size();
vector<int> prefixSum(n+1, 0);
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i-1] + (blocks[i-1] == 'W' ? 1 : 0);
}
int minW = n;
for (int i = k; i <= n; i++) {
minW = min(minW, prefixSum[i] - prefixSum[i-k]);
}
return minW;
}
int main() {
cout << minRecolors("WBBWWBBWBW", 7) << endl;
return 0;
}function minRecolorsWithPrefix(blocks, k) {
const n = blocks.length;
const prefixSum = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + (blocks[i - 1] === 'W' ? 1 : 0);
}
let minW = n;
for (let i = k; i <= n; i++) {
minW = Math.min(minW, prefixSum[i] - prefixSum[i - k]);
}
return minW;
}
console.log(minRecolorsWithPrefix('WBBWWBBWBW', 7));#include <stdio.h>
#include <string.h>
int minRecolors(char *blocks, int k) {
int n = strlen(blocks);
int prefixSum[n+1];
prefixSum[0] = 0;
// Compute prefix sum of white blocks
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i-1] + (blocks[i-1] == 'W' ? 1 : 0);
}
// Find the minimum number of white blocks in any window of size k
int minW = n;
for (int i = k; i <= n; i++) {
minW = prefixSum[i] - prefixSum[i-k] < minW ? prefixSum[i] - prefixSum[i-k] : minW;
}
return minW;
}
int main() {
char blocks[] = "WBBWWBBWBW";
int k = 7;
printf("%d\n", minRecolors(blocks, k));
return 0;
}using System;
class PrefixSumApproach {
static int MinRecolors(string blocks, int k) {
int n = blocks.Length;
int[] prefixSum = new int[n+1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i-1] + (blocks[i-1] == 'W' ? 1 : 0);
}
int minW = n;
for (int i = k; i <= n; i++) {
minW = Math.Min(minW, prefixSum[i] - prefixSum[i-k]);
}
return minW;
}
static void Main() {
Console.WriteLine(MinRecolors("WBBWWBBWBW", 7));
}
}This Python solution uses prefix sums to allow rapid determination of the number of 'W' blocks in any window, making use of computed sums to determine necessary transformations.
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).
function minimumRecolors(blocks: string, k: number): number {
let cnt = 0;
for (let i = 0; i < k; ++i) {
cnt += blocks[i] === 'W' ? 1 : 0;
}
let ans = cnt;
for (let i = k; i < blocks.length; ++i) {
cnt += blocks[i] === 'W' ? 1 : 0;
cnt -= blocks[i - k] === 'W' ? 1 : 0;
ans = Math.min(ans, cnt);
}
return ans;
}func minimumRecolors(blocks string, k int) int {
cnt := strings.Count(blocks[:k], "W")
ans := cnt
for i := k; i < len(blocks); i++ {
if blocks[i] == 'W' {
cnt++
}
if blocks[i-k] == 'W' {
cnt--
}
if ans > cnt {
ans = cnt
}
}
return ans
}impl Solution {
pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
let k = k as usize;
let s = blocks.as_bytes();
let n = s.len();
let mut count = 0;
for i in 0..k {
if s[i] == b'B' {
count += 1;
}
}
let mut ans = k - count;
for i in k..n {
if s[i - k] == b'B' {
count -= 1;
}
if s[i] == b'B' {
count += 1;
}
ans = ans.min(k - count);
}
ans as i32
}
}class Solution {
/**
* @param String $blocks
* @param Integer $k
* @return Integer
*/
function minimumRecolors($blocks, $k) {
$cnt = 0;
for ($i = 0; $i < $k; $i++) {
if ($blocks[$i] === 'W') {
$cnt++;
}
}
$min = $cnt;
for ($i = $k; $i < strlen($blocks); $i++) {
if ($blocks[$i] === 'W') {
$cnt++;
}
if ($blocks[$i - $k] === 'W') {
$cnt--;
}
$min = min($min, $cnt);
}
return $min;
}
}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 | – |
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 |
Frequently asked questions
Is Minimum Recolors to Get K Consecutive Black Blocks easy or hard?
The problem is categorized as Easy on LeetCode with an acceptance rate around 68%. It mainly tests recognition of the sliding window pattern and basic string traversal.
Minimum Recolors to Get K Consecutive Black Blocks Python/Java solution
Most implementations iterate through the string while maintaining a sliding window of size k. The logic is identical across Python, Java, C++, and JavaScript: count whites in the window, slide the window, and keep the minimum recolor count. The algorithm runs in O(n) time and O(1) space.
How to solve Minimum Recolors to Get K Consecutive Black Blocks in O(n)?
Use a sliding window of length k. Count the number of 'W' characters in the first window, then move the window forward one index at a time while updating the count. Track the minimum white count across all windows because each white block represents a recolor operation.
What is the best approach for Minimum Recolors to Get K Consecutive Black Blocks?
The sliding window approach is the most efficient and commonly expected solution. Maintain a window of size k and count how many white blocks appear inside it. As the window slides, update the count by removing the outgoing character and adding the incoming one. The minimum number of whites across all windows equals the minimum recolors needed.
Is Minimum Recolors to Get K Consecutive Black Blocks asked at Google/Amazon/Meta?
Variants of sliding window string problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern of counting characters inside a fixed window is a common interview topic.
What data structure is used in Minimum Recolors to Get K Consecutive Black Blocks?
The problem primarily uses a sliding window technique over a string. Only simple counters are required, so no advanced data structures are needed. Some alternative solutions use a prefix sum array to store cumulative counts of white blocks.
What is the time complexity of Minimum Recolors to Get K Consecutive Black Blocks?
The optimal sliding window solution runs in O(n) time where n is the length of the string. Each character enters and leaves the window at most once. The space complexity is O(1) since only a few counters are maintained.