BinarySearch 0810 Longest Repeating Sublist After K Updates

Problem statement

https://binarysearch.com/problems/Longest-Repeating-Sublist-After-K-Updates/

Solution

Equal to Leetcode 0424 Longest Repeating Character Replacement, but we need faster solution.

Complexity

It is O(n) here for time and space, see remark in leetcode problem.

Code

class Solution:
    def solve(self, s, k):
        maxf = res = 0
        count = Counter()
        for i in range(len(s)):
            count[s[i]] += 1
            maxf = max(maxf, count[s[i]])
            if res - maxf < k:
                res += 1
            else:
                count[s[i - res]] -= 1
        return res