LC 0424 [M] Longest Repeating Character Replacement - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=gqXU1UyA8pk&ab_channel=NeetCode

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        res = 0
        
        l = 0
        maxf = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count[s[r]]
            maxf = max(maxf, count[s[r]])
            
            # while (r - l + 1) - max(count.values()) > k:
            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1
                l += 1
                
            res = max(res, r - l + 1)
        return res

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freq = Counter()
        max_len = 0
        max_repeat = 0
        l = 0

        for r in range(len(s)):
            freq[s[r]] += 1
            max_repeat = max(max_repeat, freq[s[r]])

            if ((r - l + 1) - max_repeat > k):
                freq[s[l]] -= 1
                l += 1

            max_len = max(max_len, r - l + 1)

        return max_len