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

难度: Easy

给你一个长度为 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

Submission

运行时间: 14 ms

内存: 16.0 MB

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

Explain

这个题解采用了滑动窗口的方法。首先计算长度为k的初始窗口中的白色块的数量，然后将窗口向右滑动一位，并更新白色块的数量（如果新进入窗口的块是白色的，则增加1；如果离开窗口的块是白色的，则减少1）。在每次滑动窗口后，都用当前窗口中的白色块数量更新最小白色块数量。最后返回的是需要涂色的最小次数，即最少的白色块数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        n = len(blocks)
        res = cnt = blocks[:k].count('W')  # 初始化窗口内的白色块数量
        for i in range(k, n):  # 开始滑动窗口
            if blocks[i] == 'W':
                cnt += 1  # 新进入窗口的块是白色的
            if blocks[i-k] == 'W':
                cnt -= 1  # 离开窗口的块是白色的
            res = min(cnt, res)  # 更新最小白色块数量
        return res  # 返回需要涂色的最小次数

Explore

如果窗口长度k大于字符串blocks的长度n，理论上我们无法形成一个完整的窗口。在这种情况下，处理方法可以是直接返回blocks中白色块的数量，因为我们需要将所有块涂成黑色来满足获取k个黑块的要求。不过，也可以考虑抛出一个异常或返回一个特定的错误值，因为实际上不可能在长度不足的字符串中找到长度为k的连续段。

在初始化窗口时考虑前k个字符是为了简化问题的处理。从字符串的开始位置开始是一种自然且直观的方法，它可以保证窗口在后续的滑动过程中能覆盖到所有可能的k长度的连续字符段。此外，通过从固定的起始点开始，我们可以更容易地在后续操作中维护和更新窗口状态，而不需要考虑多个初始条件，从而保持算法的简洁和高效。

是的，滑动窗口方法在更新白色块数量时考虑了窗口的边界条件。代码中通过循环`for i in range(k, n)`确保了每次窗口滑动不会超出字符串的长度。当窗口滑动到字符串的末尾时，循环会自然结束，此时所有可能的窗口位置都已被检查过，确保了边界条件的处理。

不完全是这样。初始时设置`res`为`blocks[:k].count('W')`是基于第一个窗口的白色块数量作为初始的最小值开始的，这是一个启动条件。随后的每次窗口滑动都会更新这个最小值。这样的做法是为了确保我们能够找到全局的最小白色块数量，而不是假设第一个窗口就是最优解。这是一种常见的技术，在处理此类问题时先设置一个初始值，然后通过比较逐步找到最优解。