Minimum Recolors to Get K Consecutive Black Blocks Solution
Minimum Recolors to Get K Consecutive Black Blocks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Recolors to Get K Consecutive Black Blocks is an easy coding problem on strings and sliding window, asked in Amazon, Google and Accenture interviews.
- Difficulty: Easy
- Topics: Strings, Sliding Window
- Asked at: Amazon, Google, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
blocks is a string of 'W' (white) and 'B' (black) blocks. One operation recolors a single white block black.
Return the minimum number of operations needed so that somewhere in the string there are k consecutive black blocks.
Example 1
Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation: Recoloring the three whites in positions 3, 4 and 7 leaves a run of seven blacks.
Example 2
Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation: "BB" is already there.
Example 3
Input: blocks = "WWWW", k = 4
Output: 4
Constraints
1 <= k <= blocks.length <= 100blocks[i] is either 'W' or 'B'.
Hints for Minimum Recolors to Get K Consecutive Black Blocks
Hint 1
The run of
kblacks has to sit in some window of lengthk.Hint 2
The cost of a window is simply how many
'W'it holds.Hint 3
Roll that count as the window slides instead of recounting.
How to solve Minimum Recolors to Get K Consecutive Black Blocks
Any answer is realised by one window of length k, and that window costs exactly its number of white blocks. So minimise the white count over all fixed-size windows.
Approach
- Count the whites in
blocks[0 … k-1]. - Slide: when the window advances, add the entering character if it is
'W'and subtract the leaving one if it was. - Return the smallest count seen.
Why it works
Recoloring is only ever useful inside the chosen window, and each white there must be recolored exactly once, so the window's white count is its exact cost. Taking the minimum over all windows is therefore the answer.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Recounting each window is
O(n · k)— fine atn = 100but the wrong habit. - Initialising the best to 0 instead of the first window's count returns 0 always.
- Blacks are never recolored, so only
'W'contributes.
Reference solution
Python
def minimumRecolors(blocks: str, k: int) -> int:
whites = blocks[:k].count("W")
best = whites
for i in range(k, len(blocks)):
if blocks[i] == "W":
whites += 1
if blocks[i - k] == "W":
whites -= 1
best = min(best, whites)
return bestJava
public static int minimumRecolors(String blocks, int k) {
int whites = 0;
for (int i = 0; i < k; i++) if (blocks.charAt(i) == 'W') whites++;
int best = whites;
for (int i = k; i < blocks.length(); i++) {
if (blocks.charAt(i) == 'W') whites++;
if (blocks.charAt(i - k) == 'W') whites--;
best = Math.min(best, whites);
}
return best;
}C++
int minimumRecolors(string blocks, int k) {
int whites = 0;
for (int i = 0; i < k; i++) if (blocks[i] == 'W') whites++;
int best = whites;
for (int i = k; i < (int) blocks.size(); i++) {
if (blocks[i] == 'W') whites++;
if (blocks[i - k] == 'W') whites--;
best = min(best, whites);
}
return best;
}JavaScript
var minimumRecolors = function(blocks, k) {
var whites = 0;
for (var i = 0; i < k; i++) if (blocks.charAt(i) === "W") whites++;
var best = whites;
for (var j = k; j < blocks.length; j++) {
if (blocks.charAt(j) === "W") whites++;
if (blocks.charAt(j - k) === "W") whites--;
if (whites < best) best = whites;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sliding Window Technique