Minimum Recolors to Get K Consecutive Black Blocks

Minimum Recolors to Get K Consecutive Black Blocks - 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 i^th 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.

Input & Output

Example 1 — Basic Case

$ Input: blocks = "WBBWWBBW", k = 3

› Output: 1

💡 Note: We can change blocks[0] from 'W' to 'B' to get "BBBWWBBW", which has 3 consecutive black blocks at the beginning.

Example 2 — Already Optimal

$ Input: blocks = "WBWBBBWBW", k = 3

› Output: 0

💡 Note: There are already 3 consecutive black blocks (BBB) in the string, so no operations are needed.

Example 3 — All White

$ Input: blocks = "WWWWW", k = 2

› Output: 2

💡 Note: We need to change any 2 consecutive white blocks to black blocks, requiring 2 operations.

Constraints

1 ≤ blocks.length ≤ 100
blocks[i] is either 'W' or 'B'
1 ≤ k ≤ blocks.length

Visualization

Tap to expand

Understanding the Visualization

Input

String of W (white) and B (black) blocks with target k

Find Window

Find k-length window with minimum white blocks

Result

Return count of white blocks that need recoloring

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently find the k-length substring with minimum white blocks

Asked in

M Microsoft 15 a Amazon 12 A Apple 8

The sliding window approach is optimal. We maintain a window of size k and slide it across the string, efficiently counting white blocks that need to be recolored. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Optimal	O(n)	O(1)	Use sliding window technique to efficiently check all k-length substrings
Brute Force - Check All Subarrays	O(n×k)	O(1)	Check every possible substring of length k and count white blocks

Sliding Window - Optimal — Algorithm Steps

Count white blocks in first k-length window
Slide window right: remove left element, add right element
Update white count and track minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Window

Count white blocks in first k positions

Slide Right

Remove left element, add right element

Update Count

Efficiently update count and track minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* blocks, int k) {
    int n = strlen(blocks);
    
    // Count white blocks in first window
    int whiteCount = 0;
    for (int i = 0; i < k; i++) {
        if (blocks[i] == 'W') {
            whiteCount++;
        }
    }
    
    int minOperations = whiteCount;
    
    // Slide the window
    for (int i = k; i < n; i++) {
        // Remove leftmost element from window
        if (blocks[i - k] == 'W') {
            whiteCount--;
        }
        // Add rightmost element to window
        if (blocks[i] == 'W') {
            whiteCount++;
        }
        
        if (whiteCount < minOperations) {
            minOperations = whiteCount;
        }
    }
    
    return minOperations;
}

int main() {
    char blocks[100001];
    int k;
    fgets(blocks, sizeof(blocks), stdin);
    blocks[strcspn(blocks, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(blocks, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each element processed at most twice

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track window and counts

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window - Optimal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler