424. Longest Repeating Character Replacement

[fockspaces]

Hash map + sliding window

In order to check whether we can replace at most k to make the repeating substring, we can maintain a sliding window, and keep tracking the char occurance.

The valid substring: length of the window - major_occurance <= k, means we can counts the string by replacing the less than k elements.

the tricky way is to think of a hash map and keep tracking the occurance. it'll cause the O(N) time for searching the majority, don't be afraid to do this.

time complexity: O(N), actually we will get O(N*M) for the M possible choices elements. but it's constant since the uppercase character only has 26. space complexity: O(1), we need to keep track the 26 alphabets occurance.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        def is_valid_replacement(char_counts, k, length):
            return length - max(char_counts.values()) <= k
        n = len(s)
        l = -1
        ans = 0
        char_counts = {}
        for r in range(n):
            cur_char = s[r]
            # the initial case
            if l == -1:
                char_counts[cur_char] = 1
                ans, l = 1, 0
                continue
            char_counts[cur_char] = char_counts.get(cur_char, 0) + 1
            while not is_valid_replacement(char_counts, k, r - l + 1):
                char_counts[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

[fockspaces]

simplified version: actually we don't need the initial state for handling the length = 0 case. since it won't iterate in the for loop.

and the base case is l = 0, r = 1, we will count it as well.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        def is_valid_replacement(counts, k, length):
            return length - max(counts.values()) <= k
        n = len(s)
        l = 0
        ans = 0
        counts = {}
        for r in range(n):
            counts[s[r]] = counts.get(s[r], 0) + 1
            while not is_valid_replacement(counts, k, r - l + 1):
                counts[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

[fockspaces]

simplified: the max frequency we don't even need to iterate through the whole dictionary to get the max_occurance.

there's two possible value for the max_occurance

1. previous max_occurance
2. the occurance of currently updated element

we can use max_freq for maintaining the max_occurance, avoiding the iteration.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        def is_valid_replacement(max_freq, k, length):
            return length - max_freq <= k
        n = len(s)
        l = 0
        ans = 0
        counts = {}
        max_freq = 0
        for r in range(n):
            counts[s[r]] = counts.get(s[r], 0) + 1
            max_freq = max(max_freq, counts[s[r]])
            while not is_valid_replacement(max_freq, k, r - l + 1):
                counts[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans