class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if not s:
            return 0
        if k > len(s) - 2:
            return len(s)

        a = [0 for i in range(26)]
        b = [-1 for i in range(26)]

        numC = [0 for i in range(26)]

        best = k + 1

        for i in range(len(s)):
            c = ord(s[i]) - ord('A')
            numC[c] += 1

            cost = i - b[c] - 1
            b[c] = i

            oldC = 0
            while j < cost:
                c2 = s[a[c] + j + oldC]
                if c2 == c:
                    oldC += 1
                else
                    j += 1

            numC -= oldC
            a[c] += oldC + j

            best = max(best, numC + k)


        return min(best, len(s))