424. Longest Repeating Character Replacement

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

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;
    }
};

• T: $O(n)$
• S: $O(n)$