Minimum Recolors To Get K Consecutive Black Blocks

Like0

You are given a string blocks made of characters 'W' (white) and 'B' (black), and an integer k. You may recolor any white block to black. Return the minimum number of recolors needed so that at least one substring of length k becomes all black.

Think of each window of length k: the number of recolors needed for that window is exactly the number of white blocks inside it. So the task becomes finding the minimum white count over all windows of size k.

Use a fixed-size sliding window to maintain white count in O(n): add incoming character, remove outgoing character, and keep the minimum.

Example 1:

Input: blocks = "WBBWWBBWBW", k = 7

Output: 3

Explanation: The best window of length 7 has 3 white blocks, so recolor 3.

Example 2:

Input: blocks = "WBWBBBW", k = 2

Output: 0

Explanation: Window "BB" already has all black blocks.

Example 3:

Input: blocks = "WWWW", k = 2

Output: 2

Explanation: Every length-2 window has two white blocks.

Constraints: 1 <= blocks.length <= 10^5, 1 <= k <= blocks.length

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

Example 1:

Example 2:

Example 3:

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