Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        longest = 0
        counts = defaultdict(int)
        start = 0

        for end in range(len(s)):
            # add current chr to count
            counts[s[end]] += 1

            # check if window is valid (while not valid, shrink the window)
            while (end - start + 1) - max(counts.values()) > k:
                counts[s[start]] -= 1
                start += 1

            # count window length
            longest = max(end - start + 1, longest)

                
        return longest

用sliding window找出最長的substring

需要一個map，key是字母，value是出現的次數

判斷一個window是否合法：(window的長度 - map中出現最多次的字母的數量) ≥ k

• 表示，這個window中，除了出現最多次的字母以外，若要把剩下的字母換掉，k個是否足夠

初始化左指針，一開始先指向第一個位置

初始化一個map

初始化一個 result

走訪 字串，用 r 右指針

• 遇到一個字母，就在map裏面++
• while 檢查是否 valid： (window的長度 - map中出現最多次的字母的數量) ≥ k
  • 如果不valid的話，左指針走一格