class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        left = 0
        window_count = {}
        max_freq = 0

        for right, c in enumerate(s):
            window_count[c] = window_count.get(c, 0) + 1 # always add new
            window_size = right - left + 1
            max_freq = max(max_freq, window_count[c])

            if window_size - max_freq > k: # over replace
                window_count[s[left]] -= 1 # del left character
                left += 1 # move
                # no need to update max_freq, keep maximum possible window size
                # max_freq = max(max_freq, window_count[left])

            max_length = max(max_length, right - left + 1)

        return max_length

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        max_freq = 0
        max_window_size = 0
        left = 0
        for right, c in enumerate(s):
            count[c] = count.get(c, 0) + 1
            max_freq = max(max_freq, count[c])
            window_size = right - left + 1
            if window_size - max_freq > k: # invalid
                count[s[left]] -= 1
                left += 1
            # right and left move 1 step, keep the max window size same
            # and try to find the longer window
            max_window_size = max(max_window_size, right - left + 1)

        return max_window_size

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:

        ans = 0
        window_counter = defaultdict(int)
        max_counter = 0
        start = 0

        for end in range(len(s)):
            # print(start, end, s[start:end+1])
            new_word = s[end]
            window_counter[new_word] += 1
            max_counter = max(max_counter, window_counter[new_word])

            # end - start + 1 = window length (delete max duplicate <= k)
            if (end - start + 1) - max_counter <= k:
                ans = max(ans, end - start + 1)     
            else: # wrong case, move window (first delete then move)
                delete_word = s[start] 
                window_counter[delete_word] -= 1
                start += 1

        return ans