424. Longest Repeating Character Replacement

解題思路

首先，要找到「valid substring」的條件是：

substring length - max frequency letter count in substring <= k

因為最常出現的肯定是主體，剩下不常見的是要被替換的，那這些被替換的字母數量一定要小於題目規定的數字 k。

接著 substring 又是怎麼產生的？概念是 sliding window，所以就會有 left 跟 right pointer。

每次更新完 sliding window 中字母出現次數，都看該 sliding window 是 valid 的嗎？如果是，那就把 right 往右移，以及看看 ans 有無變化；如果不是，那就要把 left 往右移，以及把 count 也更新。

程式碼

class Solution {
public:
    int characterReplacement(string s, int k) {
        int count[26] = {0}, left = 0, right = 0, maxF = 0;
        int ans = 0;
        while(right < s.size())
        {
            count[s[right] - 'A']++;
            maxF = max(maxF, count[s[right] - 'A']);
            
            if((right - left + 1) - maxF > k)
            {
                count[s[left] - 'A']--;
                left++;
            }
            
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};