Minimum Recolors to Get K Consecutive Black Blocks

Easy
783.

Minimum Recolors to Get K Consecutive Black Blocks

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.

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 <= 100
  • blocks[i] is either 'W' or 'B'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} blocks
 * @param {number} k
 * @return {number}
 */
var minimumRecolors = function(blocks, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Minimum Recolors to Get K Consecutive Black Blocks

  1. Hint 1

    The run of k blacks has to sit in some window of length k.

  2. Hint 2

    The cost of a window is simply how many 'W' it holds.

  3. 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

  1. Count the whites in blocks[0 … k-1].
  2. Slide: when the window advances, add the entering character if it is 'W' and subtract the leaving one if it was.
  3. 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 at n = 100 but 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 best

Java

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