424. Longest Repeating Character Replacement - LeetCode

class Solution:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}  # counter
        mf = 0  # max_freq
        i = 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if not ((j - i + 1) - mf <= k):  # shift right
                c[s[i]] -= 1
                i += 1
        return len(s) - i  # length


class Solution2:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}
        mf, i = 0, 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if i - mf >= k:
                c[s[j - i]] -= 1
            else:
                i += 1  # update when more
        return i


class SolutionBS:  # O(log(n)) / O(n)
    # 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, i = 0, 0
            for j, char in enumerate(s):
                c[char] = c.get(char, 0) + 1
                mf = max(mf, c[char])
                if length - mf <= k:
                    return False
                if j - i + 1 > length:
                    c[s[i]] -= 1
                    i += 1
            return True

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