題目
#

leetcode 424 - Longest Repeating Character Replacement (題目說明請點連結)

題目簡述
#

給一個字串 s 和一個整數 k，請找出可以通過將最多 k 個字符替換為任意字符後，能得到的最長重複字符子字串的長度。
注意：字串只包含大寫英文字母，且替換後的子字串必須全部由相同的字符組成。

範例
#

Example 1:

Input: s = "ABAB", k = 1
Output: 3
Explanation: 可以將一個 'B' 替換為 'A'，得到 "AAAB"，最長重複字符子字串長度為 3。

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: 可以將一個 'B' 替換為 'A'，得到 "AAAABBA"，最長重複字符子字串長度為 4。

Example 3:

Input: s = "AAAA", k = 2
Output: 4
Explanation: 字串已經全部是 'A'，不需要替換，最長重複字符子字串長度為 4。

解題思路
#

這題要求我們找出可以通過最多 k 次替換得到的最長重複字符子字串。我們可以使用滑動窗口（Sliding Window）來解決這個問題，具體方法是維護一個窗口，並統計窗口內每個字符的出現次數。

解法
#

Sliding Window

使用兩個指針 left 和 right 來維護滑動窗口
統計窗口內每個字符的出現次數，並記錄最大出現次數 maxCount
當窗口大小減去最大出現次數大於 k 時，收縮左指針
更新答案為窗口大小的最大值

步驟
#

初始化：
- 創建字符計數陣列 count[26]
- 設定左指針 left = 0 和答案 ans = 0
- 設定最大出現次數 maxCount = 0
擴展窗口：
- 右指針 right 向右移動，統計字符出現次數
- 更新 maxCount 為當前最大出現次數
收縮窗口：
- 當 (right - left + 1) - maxCount > k 時，收縮左指針
- 減少左指針對應字符的計數
更新答案：
- 更新 ans 為當前窗口大小的最大值
返回結果：
- 返回 ans

例子說明
#

s = "AABABBA", k = 1

步驟	right	left	窗口	字符計數	maxCount	窗口大小	需要替換	是否收縮	答案
初始化	-	0	-	[0,0,0,…]	0	0	0	-	0
第 1 步	0	0	“A”	[1,0,0,…]	1	1	0	否	1
第 2 步	1	0	“AA”	[2,0,0,…]	2	2	0	否	2
第 3 步	2	0	“AAB”	[2,1,0,…]	2	3	1	否	3
第 4 步	3	0	“AABA”	[3,1,0,…]	3	4	1	否	4
第 5 步	4	0	“AABAB”	[3,2,0,…]	3	5	2	是	4
第 6 步	4	1	“ABAB”	[2,2,0,…]	2	4	2	是	4
第 7 步	4	2	“BAB”	[1,2,0,…]	2	3	1	否	4
第 8 步	5	2	“BABB”	[1,3,0,…]	3	4	1	否	4
第 9 步	6	2	“BABBA”	[2,3,0,…]	3	5	2	是	4

最終結果： 4

完整程式碼
#

java

class Solution {
    public int characterReplacement(String s, int k) {
        // 創建字符計數陣列，統計每個字符的出現次數
        int[] count = new int[26];
        // 左指針、答案、最大出現次數
        int left = 0, ans = 0, maxCount = 0;

        // 右指針向右移動，擴展窗口
        for(int right = 0; right < s.length(); right++){
            // 統計當前字符的出現次數
            int idx = s.charAt(right) - 'A';
            count[idx]++;
            // 更新最大出現次數
            maxCount = Math.max(maxCount, count[idx]);

            // 當窗口大小減去最大出現次數大於 k 時，收縮左指針
            while((right - left + 1) - maxCount > k){
                // 減少左指針對應字符的計數
                count[s.charAt(left) - 'A']--;
                // 左指針向右移動
                left++;
            }

            // 更新答案為當前窗口大小的最大值
            ans = Math.max(ans, right - left + 1);
        }
        
        // 返回最長重複字符子字串的長度
        return ans;
    }
}