解題程式碼

var characterReplacement = function(s, k) {
    let maxLength = 1;
    let l = 0;
    const charMap = new Map();
    let maxRepeat = 0;

    for (let i = 0; i < s.length; i++) {
        charMap.set(s[i], (charMap.get(s[i]) || 0) + 1);
        maxRepeat = Math.max(maxRepeat, charMap.get(s[i]));

        while (i - l + 1 - maxRepeat > k) {
            charMap.set(s[l], charMap.get(s[l]) - 1);
            l++;
        }
        maxLength = Math.max(maxLength, i - l + 1);
    }

    return maxLength;
};

// input = 'AABCDAAA'，k = 2
// i = 0, l = 0, maxRepeat = 1 maxLength = 1
// i = 1, l = 0, maxRepeat = 2 maxLength = 2
// i = 2, l = 0, maxRepeat = 2 maxLength = 3
// i = 3, l = 0, maxRepeat = 2 maxLength = 4
// i = 4, l = 0, maxRepeat = 2 maxLength = 4，進 while, window = ABCD，l = 1
// i = 5, l = 1, maxRepeat = 2 maxLength = 4，進 while, window = BCDA，l = 2
// i = 6, l = 2, maxRepeat = 2 maxLength = 4，進 while, window = CDAA，l = 3
// i = 7, l = 3, maxRepeat = 3 maxLength = 5，CDAAA

解題思路、演算法

這題使用 Sliding Window 解題，我們可以使用一個 hashTable 或是長度 26 個元素的陣列去儲存一個字串內各字母出現的次數，並記錄當前 window 內出現最多次的字母次數 maxRepeat，當 window size - maxRepeat <= k 時，例如 AABDA，k = 2，最多可以使用兩次去替換掉非出現最多次字母的那些字母，那 5 - 3 <= 2 成立，故 5 有可能就是題目要求的結果之一，依照這個邏輯不斷滑動窗口到字串尾端，即可找出結果。

關鍵點: maxRepeat 當有字元從 hashMap 移出時，可以不用更新，當作是維持窗口大小

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

Longest Repeating Character Replacement - Leetcode 424 - Python

贾考博 LeetCode 424. Longest Repeating Character Replacement - 滑动窗口

https://youtu.be/8iVqi8tMoKc