424. Longest Repeating Character Replacement

class Solution:
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
    def characterReplacement(self, s: str, k: int) -> int:
        c, mf = {}, 0  # counter, max_freq
        l, N = 0, len(s)
        for r in range(N):
            c[s[r]] = c.get(s[r], 0) + 1
            mf = max(mf, c[s[r]])
            if not ((r + 1) - l - mf <= k):  # shift right
                c[s[l]] -= 1
                l += 1
            # find next if same
        return N - l  # length


class Solution2:
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
    def characterReplacement(self, s: str, k: int) -> int:
        result = 0
        c, mf = {}, 0  # counter, max_freq
        for r in range(len(s)):
            c[s[r]] = c.get(s[r], 0) + 1
            mf = max(mf, c[s[r]])
            if result - mf >= k:
                c[s[r - result]] -= 1
            else:
                result += 1  # update when more
        return result


class SolutionBS:  # TODO: review
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
    def characterReplacement(self, s: str, k: int) -> int:
        def too_long(length: int):
            c, mf = {}, 0
            l = 0
            for r in range(len(s)):
                c[s[r]] = c.get(s[r], 0) + 1
                if r + 1 - l > length:
                    c[s[l]] -= 1
                    l += 1
                mf = max(mf, c[s[r]])
                if length - mf <= k:
                    return False
            return True

        l, r = 0, len(s)
        while l < r:
            m = (l + r) // 2
            length = m + 1
            l, r = (l, m) if too_long(length) else (m + 1, r)
        return (l - 1) + 1