2379. Minimum Recolors to Get K Consecutive Black Blocks

Given a binary string, consisting of 'B' (Black) and 'W' (White) blocks, and an integer K, find the minimum number of recoloring operations to get at least K consecutive 'B' blocks. Each operation allows changing a 'W' to 'B'. Return the minimum number of such operations needed.

To implement the solution, we need to utilize a sliding window approach to keep track of a window of size K over the string. As we slide the window from the start of the string to the end, we calculate the number of 'W' blocks within the window. Our goal is to find the window with the fewest 'W' blocks, as this represents the minimum number of recolor operations needed to achieve K consecutive 'B' blocks. This approach ensures optimal performance.

The time complexity of this approach is O(N), where N is the length of the string, because we pass through the string once while maintaining the count of 'W' blocks in the window. The space complexity is O(1) since we are only storing a couple of counters and pointers.

Consider the binary string "WBWBBBW" with K = 3. We slide a window of size 3 across the string:

• Window "WBW" has 2 'W', 1 'B'.
• Window "BWB" has 1 'W', 2 'B'.
• Window "WBB" has 1 'W', 2 'B'.
• Window "BBB" has 0 'W', 3 'B'. (Optimal: requires 0 recolors)
• Window "BBW" again has 1 'W', 2 'B'.

The minimum recolors required are 0, achieved by the window "BBB".

No specific frameworks are utilized but concepts of Sliding Window technique are used. Refer to Sliding Window Protocol Wiki for more information.

2025-03-08 Minimum Recolors to Get K Consecutive Black Blocks - LeetCode leetcode.com

The solution will follow the sliding window pattern to find the optimal window with minimal white blocks that need to be recolored.

/**
 * Main function to find the minimum recolors needed
 * @param {string} blocks - The binary string of 'B' and 'W' characters
 * @param {number} k - Number of consecutive blacks required
 * @returns {number} - Minimum recolor operations needed
 */
function mainSolution(blocks, k) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    function countBs(arr, start, end) {
        let acc = 0;
        for (let i = start; i < end; i++) {
            if (arr[i] === 'B') acc += 1;
        }
        return acc;
    }

    let maxB = 0;

    for (let i = 0; i + k <= blocks.length; i++) {
        const windowB = countBs(blocks, i, i + k);
        maxB = Math.max(maxB, windowB);
    }

    return k - maxB;
}

// Test cases
const testCases = [
    { blocks: "WBWBBBW", k: 3, expected: 0 },
    { blocks: "WBWBW", k: 4, expected: 2 },
    { blocks: "BBWWBBB", k: 3, expected: 0 },
    { blocks: "WWBWWB", k: 2, expected: 1 },
    { blocks: "BBBB", k: 4, expected: 0 },
];

testCases.forEach((test, index) => {
    const result = mainSolution(test.blocks, test.k);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});