# [424\. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)

- 求最長的重複子字串，可替換 `k` 次。
- 初始化兩個指標 `i` 和 `j` 分別作為滑動視窗的左右邊界，初始時都指向字串的起始位置。
- 初始化一個 `unordered_map<char, int> charCount`。
- `maxCnt` 變數為當前滑動視窗中出現次數最多的字元的次數，要不斷更新 `maxCnt` 的值。
- 什麼情況滑動視窗的左邊界要往右移呢？當`發現滑動視窗的長度 - 出現最多頻率的字母 > 可以替換的字母 k` 的時候

:::spoiler Solution

class Solution {
public:
    int characterReplacement(string s, int k)
    {
        int n = s.size();
        int longest = 0, maxCnt = 0;
        unordered_map<char, int> charCount;

        // i, j 分別是滑動視窗的左右邊界
        int i = 0;
        for (int j = 0; j < n; ++j)
        {
            // 右邊界的 freq + 1
            ++charCount[s[j]];
            
            // 更新 maxCnt 變數為當前滑動視窗中出現次數最多的字元的次數
            maxCnt = max(maxCnt, charCount[s[j]]);
            
            while (j - i + 1 - maxCnt > k)
            {
                // 移動左邊界
                // 左邊界字母的頻率 - 1
                --charCount[s[i]];
                ++i;
            }
            longest = max(longest, j - i + 1);
        }
        return longest;
    }
};

- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
:::