424. Longest Repeating Character Replacement

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)$