How can I solve the Minimum Recolors to Get K Consecutive Black Blocks problem?

Use the sliding window technique to efficiently count 'W' blocks in each k-length substring. Minimize recolors by finding the window with the fewest white blocks.

What is the time complexity of this problem?

The time complexity is O(n), as the sliding window only needs to traverse the string once and update the count in constant time.

Why is a sliding window approach the best method for this problem?

A sliding window minimizes redundant work by efficiently maintaining the count of 'W' blocks within each window, leading to an optimal O(n) time complexity.

What is the space complexity of the Minimum Recolors to Get K Consecutive Black Blocks problem?

The space complexity is O(1), as the solution only requires a constant amount of additional space to track the window state.

Can this problem be solved using brute force?

While brute force could work, it would be inefficient with a time complexity of O(n * k). The sliding window approach is much more optimal with O(n) time.

#2379

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

得到 K 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ， blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。给你一个整数 k ，表示想要连续黑色块的数目。每一次操作中，你可以选择一个白色块将它涂成黑色块。请你…

字符串滑动窗口

题目描述

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要连续黑色块的数目。

每一次操作中，你可以选择一个白色块将它涂成黑色块。

请你返回至少出现一次连续 k 个黑色块的最少操作次数。

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

提示：

n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n

lightbulb

解题思路

方法一：滑动窗口

我们观察发现，题目实际上求的是一个 $k$ 大小的滑动窗口中白色块的最小数量。

因此，我们只需要遍历字符串 $blocks$ ，用一个变量 $cnt$ 统计当前窗口中白色块的数量，然后用一个变量 $ans$ 维护最小值即可。

遍历结束后即可得到答案。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $blocks$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        ans = cnt = blocks[:k].count('W')
        for i in range(k, len(blocks)):
            cnt += blocks[i] == 'W'
            cnt -= blocks[i - k] == 'W'
            ans = min(ans, cnt)
        return ans

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidates should be able to recognize that a sliding window approach is optimal for this problem.
question_mark
Watch for the ability to efficiently update the window state with minimal overhead as the window slides.
question_mark
Look for candidates who can quickly explain the efficiency of the O(n) time complexity and O(1) space complexity.

warning

常见陷阱

外企场景

error
Not recognizing that the problem can be solved with a sliding window, leading to inefficient brute force approaches.
error
Failing to update the window's state efficiently as it slides, causing unnecessary recalculations.
error
Misunderstanding the constraints and not considering that the window must be exactly size k, potentially leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where k is larger or smaller relative to n, or the string is heavily biased toward one color.
arrow_right_alt
What if the problem asked for at least m consecutive black blocks, where m is variable and provided as an input?
arrow_right_alt
Instead of counting 'W' blocks, what if the problem required finding the most efficient way to create exactly k consecutive black blocks without exceeding it?

help

常见问题

外企场景

继续练习

#2269 找到一个数字的 K 美丽值 #2516 每种字符至少取 K 个 #2156 查找给定哈希值的子串