DAY 27 試題

問題描述

給定一個字串 s 和一個整數 k，你可以選擇字串中的任意一個字符並將其更改為任何其他的大寫英文字母。最多可以執行這個操作 k 次。請返回在上述操作後，能夠得到的最長的只包含相同字母的子字串長度。

範例 1：

• 輸入：s = "ABAB", k = 2
• 輸出：4
• 解釋：將兩個 A 替換為兩個 B 或將兩個 B 替換為兩個 A，結果可以得到長度為 4 的相同字符子字串。

範例 2：

• 輸入：s = "AABABBA", k = 1
• 輸出：4
• 解釋：將中間的 A 替換為 B，可以形成 "AABBBBA"，其中 "BBBB" 是長度為 4 的最長相同字符子字串。

限制條件：

• 1 <= s.length <= 10^5
• s 只包含大寫英文字母。
• 0 <= k <= s.length

解題思路

這題要求我們找到能夠通過最多 k 次字符替換後形成的最長只包含相同字符的子字串。由於只允許 k 次字符替換，這意味著我們需要找到某個子串，該子串中最多有 k 個字符與目標字符不同。

為了解決這個問題，我們可以使用「滑動視窗」方法來遍歷字串，並且維持當前視窗中的字母出現次數。在每個時刻，我們可以計算出能夠通過替換獲得的最大相同字符子串。

具體步驟如下：

1. 使用滑動視窗保持當前處理的子串區間。
2. 使用一個變量來追蹤當前視窗中最常出現的字符的頻率。
3. 如果視窗中需要替換的字符數量超過 k，就需要縮小視窗範圍。
4. 記錄每次擴展視窗時的最長子串長度。

class Solution {
public:
    int characterReplacement(string s, int k) {
        unordered_map<char, int> count;
        int max_count = 0;  // 當前視窗中最多的相同字母的個數
        int left = 0;       // 左指針
        int result = 0;     // 最長子串的長度

        for (int right = 0; right < s.size(); ++right) {
            count[s[right]]++;
            max_count = max(max_count, count[s[right]]);
            
            // 若需要替換的字符數量大於 k，則縮小視窗
            if (right - left + 1 - max_count > k) {
                count[s[left]]--;  // 減少左指針字符的計數
                left++;  // 左指針右移
            }
            
            // 記錄當前視窗的最大長度
            result = max(result, right - left + 1);
        }
        
        return result;
    }
};

解法重點與分析

1. 滑動視窗技術：

• 我們使用兩個指針 left 和 right 來維持一個滑動視窗，該視窗用來表示當前考慮的子串。
• right 指針向右擴展子串，left 指針根據條件來縮小子串。

2. 視窗內最多相同字符的計算：

• 利用一個哈希表（unordered_map<char, int>）來記錄當前視窗內每個字符的出現次數。
• max_count 用來記錄當前視窗內最多的相同字符數量，這有助於我們判斷是否需要縮小視窗。

3. 條件判斷與視窗調整：

• 當前視窗的長度為 right - left + 1，如果其中需要替換的字符數（即視窗總長度減去最多字符的數量）超過了 k，則需要移動左指針以縮小視窗。

4. 最長子串的計算：

• 在遍歷的過程中，不斷更新我們找到的最長有效子串的長度。

5. 時間複雜度：O(n)，其中 n 是字串的長度。我們只需遍歷一次字串，並且每次操作中更新哈希表的時間為常數。

6. 空間複雜度：O(1)，因為哈希表的大小在最壞情況下最多是 26 個字母，因此我們的空間複雜度是常數級別。

總結

這道題使用滑動視窗技術來解決，通過維持當前視窗中的字符出現次數，並利用最大相同字符的頻率來判斷是否需要縮小視窗。這種解法可以有效地在 O(n) 時間內找到答案，並且適合處理長度較大的字串。

以上是第二十七天的自學內容分享，謝謝大家。