Solutions

# Sliding window. Window size - count of most frequent char <= k.
# sliding-window

# Brute force - O(N^2) time | O(m) space (m: unique chars in s)
def characterReplacement(s: str, k: int) -> int:
    res = 0
    for l in range(len(s)):
        freq = {}
        maxf = 0
        for r in range(l, len(s)):
            freq[s[r]] = freq.get(s[r], 0) + 1
            maxf = max(maxf, freq[s[r]])
            if (r -l +1) -maxf <=k:
                res = max(res, r -l +1)

    return res

# Sliding window - O(N * m) time | O(m) space (m: unique chars in s)
def characterReplacement(s: str, k: int) -> int:
    charset = set(s)
    res = 0
    for c in charset:
        l = 0
        count = 0
        for r in range(len(s)):
            if s[r] == c:
                count += 1

            while (r -l +1) - count > k:
                if s[l] == c:
                    count -= 1
                l += 1
            res = max(res, (r-l +1))
    return res

# Sliding window optimized - O(N) time | O(m) space (m: unique chars in s)
def characterReplacement(s: str, k: int) -> int:
    res = 0
    freq = {}
    maxf = 0
    l = 0
    for r in range(len(s)):
        freq[s[r]] = freq.get(s[r], 0) +1
        maxf = max(maxf, freq[s[r]])

        while (r -l +1) - maxf > k:
            freq[s[l]] -= 1
            l += 1

        res = max(res, (r -l +1))
    return res