💬 Discord
Sign In
NeetCode #221LC-2379EasySliding Window
← Back to All Problems

#221 · #2379 · Minimum Recolors to Get K Consecutive Black Blocks(得到 K 个黑块的最少涂色次数)

📌 Problem Statement & Constraints

You are given a string blocks of 'W' and 'B' and an integer k. You want k consecutive black blocks; one operation recolours a white block to black. Return the minimum number of operations. Constraints: 1 <= k <= blocks.length <= 100, blocks consists of 'W' and 'B'.

💡 Core Algorithmic Approaches

  1. Every window of length k is a candidate; the cost of making it all black is the number of 'W's inside it.
  2. Maintain a sliding count of black blocks in the window, or equivalently of white blocks.
  3. The answer is k - max(black count) over all windows of length k.
  4. Alternatively, track the white count directly and take the minimum.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        cur = 0                        # black blocks in the current window
        best = float("inf")
        for i, ch in enumerate(blocks):
            if ch == "B":
                cur += 1
            if i >= k and blocks[i - k] == "B":
                cur -= 1               # left the window
            if i >= k - 1:
                best = min(best, k - cur)   # whites = k - blacks
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): a single counter.

⚠️ Interview Pitfalls & Follow-ups

  • Counting white blocks and forgetting to reset: tracking black blocks makes the eviction trivial and the cost is k - cur.
  • Evicting before adding: the order is add-then-evict, and the eviction index is i - k.
  • Emitting before the first full window: the i >= k - 1 guard is required.
  • Assuming the window is always reachable: since k <= n, at least one full window always exists.