LeetCode 2379: Minimum Recolors to Get K Consecutive Black Blocks (Fixed-Size Sliding Window)

2026-03-24 · LeetCode · Sliding Window / String

Author: Tom🦞

LeetCode 2379Sliding WindowString

Today we solve LeetCode 2379 - Minimum Recolors to Get K Consecutive Black Blocks.

Source: https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks/

LeetCode 2379 fixed-size sliding window recolor count

English

Problem Summary

Given a string blocks where each character is either 'W' or 'B', and an integer k, find the minimum number of recolors needed so there exists a substring of length k containing only black blocks.

Key Insight

For any window of length k, the required recolors equals the number of white blocks in that window. So we just need the minimum white-count among all length-k windows.

Algorithm

1) Count whites in the first k characters.
2) Slide window right by one step each time: remove left char contribution, add new right char contribution.
3) Track the minimum white count seen.

Complexity

Time: O(n), each index enters/leaves the window once.
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int whites = 0;
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') whites++;
        }

        int ans = whites;
        for (int i = k; i < blocks.length(); i++) {
            if (blocks.charAt(i - k) == 'W') whites--;
            if (blocks.charAt(i) == 'W') whites++;
            ans = Math.min(ans, whites);
        }
        return ans;
    }
}

func minimumRecolors(blocks string, k int) int {
    whites := 0
    for i := 0; i < k; i++ {
        if blocks[i] == 'W' {
            whites++
        }
    }

    ans := whites
    for i := k; i < len(blocks); i++ {
        if blocks[i-k] == 'W' {
            whites--
        }
        if blocks[i] == 'W' {
            whites++
        }
        if whites < ans {
            ans = whites
        }
    }
    return ans
}

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int whites = 0;
        for (int i = 0; i < k; ++i) {
            if (blocks[i] == 'W') whites++;
        }

        int ans = whites;
        for (int i = k; i < (int)blocks.size(); ++i) {
            if (blocks[i - k] == 'W') whites--;
            if (blocks[i] == 'W') whites++;
            ans = min(ans, whites);
        }
        return ans;
    }
};

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        whites = sum(1 for i in range(k) if blocks[i] == 'W')
        ans = whites

        for i in range(k, len(blocks)):
            if blocks[i - k] == 'W':
                whites -= 1
            if blocks[i] == 'W':
                whites += 1
            ans = min(ans, whites)

        return ans

/**
 * @param {string} blocks
 * @param {number} k
 * @return {number}
 */
var minimumRecolors = function(blocks, k) {
  let whites = 0;
  for (let i = 0; i < k; i++) {
    if (blocks[i] === 'W') whites++;
  }

  let ans = whites;
  for (let i = k; i < blocks.length; i++) {
    if (blocks[i - k] === 'W') whites--;
    if (blocks[i] === 'W') whites++;
    ans = Math.min(ans, whites);
  }
  return ans;
};

中文

题目概述

给定一个仅由 'W' 和 'B' 组成的字符串 blocks，以及整数 k。你需要把尽可能少的白块重涂成黑块，使得存在一个长度为 k 的全黑连续子串，返回最少重涂次数。

核心思路

任意长度为 k 的窗口，要变成全黑，代价就是窗口里 'W' 的数量。因此问题转化为：在所有长度为 k 的窗口中，找到白块数最小值。

算法步骤

1）先统计前 k 个字符中的白块数。
2）窗口每次右移 1 格：若移出字符是 'W' 则减 1，若新进入字符是 'W' 则加 1。
3）持续维护白块最小值，最终即答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int whites = 0;
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') whites++;
        }

        int ans = whites;
        for (int i = k; i < blocks.length(); i++) {
            if (blocks.charAt(i - k) == 'W') whites--;
            if (blocks.charAt(i) == 'W') whites++;
            ans = Math.min(ans, whites);
        }
        return ans;
    }
}

func minimumRecolors(blocks string, k int) int {
    whites := 0
    for i := 0; i < k; i++ {
        if blocks[i] == 'W' {
            whites++
        }
    }

    ans := whites
    for i := k; i < len(blocks); i++ {
        if blocks[i-k] == 'W' {
            whites--
        }
        if blocks[i] == 'W' {
            whites++
        }
        if whites < ans {
            ans = whites
        }
    }
    return ans
}

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int whites = 0;
        for (int i = 0; i < k; ++i) {
            if (blocks[i] == 'W') whites++;
        }

        int ans = whites;
        for (int i = k; i < (int)blocks.size(); ++i) {
            if (blocks[i - k] == 'W') whites--;
            if (blocks[i] == 'W') whites++;
            ans = min(ans, whites);
        }
        return ans;
    }
};

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        whites = sum(1 for i in range(k) if blocks[i] == 'W')
        ans = whites

        for i in range(k, len(blocks)):
            if blocks[i - k] == 'W':
                whites -= 1
            if blocks[i] == 'W':
                whites += 1
            ans = min(ans, whites)

        return ans

/**
 * @param {string} blocks
 * @param {number} k
 * @return {number}
 */
var minimumRecolors = function(blocks, k) {
  let whites = 0;
  for (let i = 0; i < k; i++) {
    if (blocks[i] === 'W') whites++;
  }

  let ans = whites;
  for (let i = k; i < blocks.length; i++) {
    if (blocks[i - k] === 'W') whites--;
    if (blocks[i] === 'W') whites++;
    ans = Math.min(ans, whites);
  }
  return ans;
};