Minimum Recolors To Get K Consecutive Black Blocks

Like0

In Minimum Recolors To Get K Consecutive Black Blocks, you receive a string blocks made of 'W' and 'B', plus an integer k. You can recolor white blocks to black, and you need the minimum number of recolors required so at least one contiguous segment of length k becomes fully black.

The key idea is simple: for any window of size k, the number of recolors needed is exactly how many 'W' characters are in that window. So the real task is finding the minimum white count among all length-k windows. A fixed sliding window makes this efficient: initialize the first window, then update counts as one character enters and one leaves.

The judge checks easy and tricky scenarios, including already-black windows requiring zero changes, all-white stretches, and alternating patterns where only one recolor may be needed. Your function should return a single integer minimum, with no extra output, and the answer must be based on contiguous windows only for every tested case.

Examples

Example 1

Input

blocks = "WBBWWBBWBW", k = 7

Output

Explanation

Best size-7 window contains 3 white blocks.

Example 2

Input

blocks = "WBWBBBW", k = 2

Output

Explanation

Window "BB" already satisfies the requirement.

Example 3

Input

blocks = "WWWW", k = 2

Output

Explanation

Need to recolor both blocks in any window.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Recolors To Get K Consecutive Black Blocks - Budibadu

Best Answers

java

class Solution {
    public int minimum_recolors_to_get_k_consecutive_black_blocks(String blocks, int k) {
        int n = blocks.length();
        if (k <= 0 || k > n) return 0;
        int white = 0;
        for (int i = 0; i < k; i++) if (blocks.charAt(i) == 'W') white++;
        int best = white;
        for (int i = k; i < n; i++) {
            if (blocks.charAt(i) == 'W') white++;
            if (blocks.charAt(i-k) == 'W') white--;
            if (white < best) best = white;
        }
        return best;
    }
}

javascript

function minimum_recolors_to_get_k_consecutive_black_blocks(blocks, k) {
    var n = blocks.length;
    if (k <= 0 || k > n) return 0;
    var white = 0;
    for (var i = 0; i < k; i++) if (blocks.charAt(i) === "W") white++;
    var best = white;
    for (var j = k; j < n; j++) {
        if (blocks.charAt(j) === "W") white++;
        if (blocks.charAt(j-k) === "W") white--;
        if (white < best) best = white;
    }
    return best;
}

php

<?php
function minimum_recolors_to_get_k_consecutive_black_blocks($blocks, $k) {
    $n = strlen($blocks);
    if ($k <= 0 || $k > $n) return 0;
    $white = 0;
    for ($i = 0; $i < $k; $i++) if ($blocks[$i] === "W") $white++;
    $best = $white;
    for ($i = $k; $i < $n; $i++) {
        if ($blocks[$i] === "W") $white++;
        if ($blocks[$i-$k] === "W") $white--;
        if ($white < $best) $best = $white;
    }
    return $best;
}
?>

python

def minimum_recolors_to_get_k_consecutive_black_blocks(blocks: str, k: int) -> int:
    n = len(blocks)
    if k <= 0 or k > n:
        return 0
    white = 0
    for i in range(k):
        if blocks[i] == "W":
            white += 1
    best = white
    for i in range(k, n):
        if blocks[i] == "W":
            white += 1
        if blocks[i-k] == "W":
            white -= 1
        if white < best:
            best = white
    return best

rust

fn minimum_recolors_to_get_k_consecutive_black_blocks(blocks: String, k: i32) -> i32 {
    let chars: Vec<char> = blocks.chars().collect();
    let n = chars.len();
    if k <= 0 { return 0; }
    let ku = k as usize;
    if ku > n { return 0; }
    let mut white = 0;
    for i in 0..ku { if chars[i] == 'W' { white += 1; } }
    let mut best = white;
    for i in ku..n {
        if chars[i] == 'W' { white += 1; }
        if chars[i-ku] == 'W' { white -= 1; }
        if white < best { best = white; }
    }
    best
}

typescript

function minimum_recolors_to_get_k_consecutive_black_blocks(blocks: string, k: number): number {
    var n = blocks.length;
    if (k <= 0 || k > n) return 0;
    var white = 0;
    for (var i = 0; i < k; i++) if (blocks.charAt(i) === "W") white++;
    var best = white;
    for (var j = k; j < n; j++) {
        if (blocks.charAt(j) === "W") white++;
        if (blocks.charAt(j-k) === "W") white--;
        if (white < best) best = white;
    }
    return best;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Minimum Recolors To Get K Consecutive Black Blocks

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Sliding Window Problems

Balanced Triplets Subarray

Maximum Sum Subarray Size K

First Negative In Every Window

Maximum Vowels In Substring Length K

Contains Nearby Duplicate Window

Comments (0)

Join the Discussion