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

        a = [-k for i in range(26)]
        b = [0 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]
            b[c] = i + 1


            oldC = 0
            j = 0


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

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

            best = max(best, numC[c] + k)


        return min(best, len(s))