題目資訊

題目編號: 2379
題目連結: Minimum Recolors to Get K Consecutive Black Blocks
主題: String, Sliding Window

題目敘述

給定一個0-索引的字串 blocks，長度為 $n$，其中 blocks[i] 不是 'W' 就是 'B'，代表第 $i^{th}$ 個方塊的顏色。字符 'W' 和 'B' 分別表示顏色白色與黑色。

另外，給定一個整數 k，這是期望的連續黑色方塊數量。

在一次操作中，你可以重新著色一個白色方塊，使其成為黑色方塊。

回傳所需的最少操作次數，使得至少有一個出現 k 個連續黑色方塊的情況。

範例 1:

Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
說明：
達成7個連續黑色方塊的一種方式是將第0、3、4個方塊重新著色，
使得 blocks = "BBBBBBBWBW"。
可以證明，沒有任何辦法能以少於3次的操作達成7個連續黑色方塊。
因此，我們回傳3。

範例 2:

Input: blocks = "WBWBBBW", k = 2
Output: 0
說明：
不需要進行任何變更，因為已經存在2個連續黑色方塊。
因此，我們回傳0。

約束條件:

$n == \text{blocks.length}$
$1 \leq n \leq 100$
$blocks[i]$ 不是 'W' 就是 'B'。
$1 \leq k \leq n$

直覺

這個問題涉及將一段由黑色 ('B') 和白色 ('W') 方塊組成的字串轉換為至少有 k 個連續黑色方塊的序列。允許的操作是將白色方塊重新著色為黑色，而目標是將重新著色的操作數量最小化。這可被視為一個典型的滑動視窗（sliding window）問題，我們希望找到一個長度為 k 的視窗，其中已有最多的黑色方塊。根據這個資訊，我們可以確定為達到預期的序列所需的重新著色操作數量。

解法

該解法利用滑動視窗技術來高效計算最小重新著色操作數量。關鍵步驟如下：

初始化黑色方塊計數： 開始時，計算長度為 k 的第一個視窗中黑色方塊的數量。這將幫助我們設置初始視窗並計算其所需的操作數量。
計算初始操作： 透過從 k 中減去該視窗中黑色方塊的數量，確定將第一個視窗轉換為 k 個連續黑色方塊所需的初始操作數量。
滑動視窗： 以一個方塊的幅度滑動視窗遍歷整個字串。對於每一步：
- 將下一個方塊納入視窗內，並更新黑色方塊的計數。
- 將前一個方塊排除出視窗，並相應地更新黑色方塊的計數。
- 重新計算當前視窗達到 k 個連續黑色方塊所需的最小操作數，具體是計算該視窗內白色方塊的數量。
更新最小操作數： 隨著視窗在字串上滑動，持續更新發現的最小操作數。
返回結果： 當視窗遍歷完整個字串後，所儲存的最小操作數就是問題的答案。

這種方法確保我們有效地找到了需要最少重新著色操作的視窗，從而以最小的計算開銷解決問題。

程式碼

C++

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int blackCount = 0;

        // 計算第一個大小為 k 的窗口中的黑色方塊數量
        for (int i = 0; i < k; i++) {
            if (blocks[i] == 'B') {
                blackCount++;
            }
        }

        // 初始答案是第一個窗口中的白色方塊數量
        int minOperations = k - blackCount;

        // 將窗口滑過整個字串
        for (int i = 0; i < blocks.size() - k; i++) {
            // 將下一個方塊包含到窗口中
            if (blocks[i + k] == 'B') {
                blackCount++;
            }

            // 將前一個方塊從窗口中排除
            if (blocks[i] == 'B') {
                blackCount--;
            }
            
            // 更新達成 k 個連續黑色方塊所需的最小操作數
            minOperations = min(minOperations, k - blackCount);
        }

        return minOperations;
    }
};

Python

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        blackCount = 0

        # 計算第一個大小為k的視窗中黑色方塊的數量
        for i in range(k):
            if blocks[i] == 'B':
                blackCount += 1

        # 初始答案為第一個視窗中白色方塊的數量
        minOperations = k - blackCount

        # 將視窗滑動遍歷整個字串
        for i in range(len(blocks) - k):
            # 將下一個方塊包含進視窗中
            if blocks[i + k] == 'B':
                blackCount += 1

            # 將前一個方塊從視窗中排除
            if blocks[i] == 'B':
                blackCount -= 1
            
            # 更新達成k個連續黑色方塊所需的最少操作次數
            minOperations = min(minOperations, k - blackCount)

        return minOperations

複雜度分析

時間複雜度: $O(n)$
該演算法使用滑動窗口方法，窗口大小固定為 $k$。最初，它計算第一個大小為 $k$ 的窗口中的黑塊數量。此操作需要 $O(k)$ 的時間。然後，將窗口從下一個位置滑動到字符串的末端，在窗口移動時需要 $O(n-k)$ 的操作來調整黑塊的數量。因此，總的時間複雜度為 $O(k) + O(n-k) = O(n)$。
空間複雜度: $O(1)$
該演算法使用恒定量的額外空間，無論輸入大小如何。它使用一些整數變量來追蹤計數並存儲所需的最小操作數。因此，空間複雜度是 $O(1)$。

CS Note
En

Leetcode 2379. Minimum Recolors to Get K Consecutive Black Blocks

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析