Scale Engineer

Minimum Recolors to Get K Consecutive Black Blocks

Easy
#2165Time: O(n * k), where `n` is the length of the string and `k` is the window size. The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k` times.Space: O(1), as we only use a few variables to store counts and indices, requiring constant extra space.1 company
Patterns
Sliding Window
Data structures
String
Companies
HP

Prompt

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.length
  • 1 <= n <= 100
  • blocks[i] is either 'W' or 'B'.
  • 1 <= k <= n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible consecutive subarrays (windows) of length k. For each window, it counts the number of white blocks ('W'), which represents the number of operations needed for that specific window. The minimum count found across all windows is the answer.

Algorithm

  • Initialize a variable minOperations to k, which is the maximum possible number of operations.
  • Iterate through the string with an index i from 0 to n - k, where n is the length of blocks. This index i represents the starting position of a window.
  • For each starting position i, initialize a counter currentWhiteBlocks to 0.
  • Create a nested loop with an index j from i to i + k - 1 to iterate through the current window of size k.
  • Inside the inner loop, if the character blocks.charAt(j) is 'W', increment currentWhiteBlocks.
  • After the inner loop finishes, the currentWhiteBlocks holds the number of recolors needed for the window starting at i.
  • Update minOperations by taking the minimum of its current value and currentWhiteBlocks.
  • After the outer loop completes, minOperations will contain the minimum number of recolors required across all possible windows. Return minOperations.

Walkthrough

The algorithm works by checking every possible starting position for a sequence of k consecutive blocks. An outer loop iterates from the start of the string up to the last possible starting point for a window of size k (i.e., n-k). For each starting position, an inner loop iterates k times to examine the characters within that window. Inside the inner loop, we count the number of 'W' characters. This count is the number of recolors required for the current window. We maintain a variable, minOperations, initialized to a large value (or k), and update it with the minimum white block count found so far. After checking all possible windows, minOperations will hold the minimum number of recolors needed.

class Solution {    public int minimumRecolors(String blocks, int k) {        int n = blocks.length();        int minOperations = k; // At most k operations are needed         // Iterate through all possible start positions of a window of size k        for (int i = 0; i <= n - k; i++) {            int currentWhiteBlocks = 0;            // Count white blocks in the current window [i, i+k-1]            for (int j = i; j < i + k; j++) {                if (blocks.charAt(j) == 'W') {                    currentWhiteBlocks++;                }            }            // Update the minimum operations needed            minOperations = Math.min(minOperations, currentWhiteBlocks);        }        return minOperations;    }}

Complexity

Time

O(n * k), where `n` is the length of the string and `k` is the window size. The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k` times.

Space

O(1), as we only use a few variables to store counts and indices, requiring constant extra space.

Trade-offs

Pros

  • It is straightforward to understand and implement.

  • It correctly solves the problem and is acceptable for small constraints.

Cons

  • This approach is less efficient due to redundant computations. For each window, it recounts all the 'W's, even though adjacent windows have many overlapping characters.

Solutions

class Solution {public  int minimumRecolors(String blocks, int k) {    int cnt = 0;    for (int i = 0; i < k; ++i) {      cnt += blocks.charAt(i) == 'W' ? 1 : 0;    }    int ans = cnt;    for (int i = k; i < blocks.length(); ++i) {      cnt += blocks.charAt(i) == 'W' ? 1 : 0;      cnt -= blocks.charAt(i - k) == 'W' ? 1 : 0;      ans = Math.min(ans, cnt);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem