題目資訊

• 題目編號: 424
• 題目連結: Longest Repeating Character Replacement
• 主題: Hash Table, String, Sliding Window

題目敘述

你有一個字串 s 和一個整數 k。你可以選擇字串中的任何一個字元，將其更改為任何其他大寫英文字母。你最多可以進行此操作 $k$ 次。

返回在執行上述操作後，可以得到的具有相同字母的最長子字串的長度。

範例 1:

輸入: s = “ABAB”, k = 2
輸出: 4
解釋: 將兩個 ‘A’ 替換為兩個 ‘B’ 或反之亦然。

範例 2:

輸入: s = “AABABBA”, k = 1
輸出: 4
解釋: 將中間的一個 ‘A’ 替換為 ‘B’，形成 “AABBBBA”。子字串 “BBBB” 具有最長的重複字母，其長度為 4。也可能存在其他方法可以達到此答案。

約束條件:

• $1 \leq s.length \leq 10^5$
• $s$ 僅由大寫英文字母組成。
• $0 \leq k \leq s.length$

直覺

這個問題主要是關於在允許最多 $k$ 次的修改下，最大化由相同字符組成的子字串的長度。關鍵的洞察在於利用滑動窗口的方法結合字符頻率計數，窗口會動態調整以維持在允許修改次數內的可行性。這使得我們可以在保持約束的同時，有效地探索整個字串的潛在解決方案。

解法

此解法使用滑動窗口技術，並且利用兩個指針 left 和 right 來定義字串中的當前窗口範圍。當 right 遍歷字串時，使用固定大小為26的向量 charCount 來跟蹤當前窗口內每個字符的頻率（代表每一個大寫英文字母）。

1. 初始化:

   • 初始化 left 和 right 指針為字串的開頭位置。
   • 將 maxLength 初始化為0，用以儲存發現的最長有效子字串的長度。
   • 初始化 charCount 向量來記錄當前窗口內每個字符的頻率。

2. 滑動窗口擴展：

   • 漸增 right 指標以擴展窗口。
   • 為 right 位置的字符更新 charCount 中相應的字符計數。

3. 有效性檢查：

   • 對於從 left 到 right 的當前窗口，計算需要將所有字符變為相同所需的更改次數。這由 right - left + 1 - max_count 給出，其中 max_count 是當前窗口中最常見字符的頻率。
   • 如果所需的更改次數超過 $k$，則增長 left 指針從左縮小窗口，直到窗口再次有效。同時調整 left 位置字符的頻率，因為它不再位於窗口內。

4. 更新結果：

   • 計算當前有效窗口的長度（right - left + 1），並在這個窗口更長時更新 maxLength。

5. 終止：

   • 當 right 完全遍歷整個字串後，maxLength 就是最長有效子字串的長度。

該演算法有效地在線性時間 $O(n)$ 內計算解決方案，其中 $n$ 為字串的長度，運用了滑動窗口和字符頻率計數的方法。

程式碼

C++

class Solution {
public:
    int characterReplacement(string s, int k) {
        // 向量來計算每個字符的出現次數
        vector<int> charCount(26, 0);
        
        int left = 0, right = 0;
        int maxLength = 0;

        // 使用右指針滑動視窗
        for (; right < s.size(); right++) {
            // 更新當前字符的計數
            charCount[s[right] - 'A']++;

            // 檢查當前視窗是否有效        
            while (right - left + 1 - *max_element(charCount.begin(), charCount.end()) > k) {
                // 若無效，從左邊縮小視窗
                charCount[s[left] - 'A']--;
                left++;
            }

            // 更新目前發現的最大長度
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 用來計算每個字元出現次數的清單
        charCount = [0] * 26
        
        left = 0
        right = 0
        maxLength = 0

        # 使用 'right' 指針滑動視窗
        while right < len(s):
            # 更新當前字元的計數
            charCount[ord(s[right]) - ord('A')] += 1

            # 檢查當前視窗是否有效        
            while right - left + 1 - max(charCount) > k:
                # 如果無效，則從左側縮小視窗
                charCount[ord(s[left]) - ord('A')] -= 1
                left += 1

            # 更新目前找到的最大長度
            maxLength = max(maxLength, right - left + 1)
            right += 1

        return maxLength

複雜度分析

• 時間複雜度: $O(n)$

  演算法使用滑動窗口方法，左右指針遍歷字串 $s$，並且每個字元只停止一次。迴圈內的操作，包括計算字元和檢查固定大小向量（大小為26，對應於大寫英文字母數量）中的最大元素，耗費常數時間 $O(1)$。因此，整體時間複雜度為線性 $O(n)$，其中 $n$ 是字串 $s$ 的長度。

• 空間複雜度: $O(1)$

  演算法使用的空間是常數 $O(1)$，因為它涉及一個固定大小為26的向量來儲存字元計數，無論輸入大小 $n$ 如何。此外，用於指標和最大長度的額外變數也使用固定量的空間，這不會隨著輸入的增長而增加。