Problem statement

https://leetcode.com/problems/longest-repeating-character-replacement/

Solution

Reformulate: find the substring of biggest length, such that its length - amount of the most frequent symbol is less or equal to k (we call it characteristic). We can do it, using sliding window: we keep frequencies of all symbols in window. We extend our window to the right until it is possible and remove symbols form the left if needed. The main difficulty is to keep maximum frequency of element in our window, we can do it in O(k), where k is the size of alphabet.

Complexity

Overall complexity is O(nk) if we use list, and find maximum in list, space complexity is O(k).

Code

class Solution:
    def characterReplacement(self, s, k):
        beg, end = 0, 0
        wind, max_freq, ans = [0] * 26, 0, 0
        while end < len(s):
            new = ord(s[end]) - ord("A")
            if end + 1 - beg - max(max_freq, wind[new] + 1) <= k:
                end += 1
                wind[new] += 1
                max_freq = max(max_freq, wind[new])
                ans = max(ans, end - beg)
            else:
                wind[ord(s[beg]) - ord("A")] -= 1
                beg += 1
                max_freq = max(wind)
                
        return ans

Remark

In fact we can comment line max_freq = max(wind), that is recalculating our maximum frequency when we delete symbol: it will make complexity O(n), however in practice it works not much faster. At the moment I do not completely understand the reason, there is some greedy idea here.