unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 424: Longest Repeating Character Replacement

link

We can convert any k characters to any other character.

Say in a substring of s, the char c has the most frequency. We should try matching other characters in the window to c using k replacements. In other words, as long as window_length – count_of[c] \le k, the window is good. Longer windows can be good only if count_of[c] is higher.

So, we evaluate if a window is good based on the max frequency of any char seen so far. Above, window2 beats window1 because, the max frequency seen so far (count_of[“A”] = 3) is smaller than the new max frequency: count_of[“C”] = 4.

Time: \mathcal{O}(n), space: \mathcal{O}(\texttt{alphabet-size}).

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count_of = {}
        max_freq = 0
        max_len = 0
        begin = 0
        for end, c in enumerate(s):
            if c not in count_of:
                count_of[c] = 1
            else:
                count_of[c] += 1
            max_freq = max(max_freq, count_of[c])
            
            window_len = end-begin+1
            if window_len - max_freq <= k:
                max_len = max(max_len, window_len)
            else:
                del_char = s[begin]
                count_of[del_char] -= 1
                begin += 1
        
        return max_len

tanvirdotzaman

,

Leave a comment