424. Longest Repeating Character Replacement

Medium

Problem:

Given a string s composed of uppercase letters, output the longest length of a consecutive repeating substring that can be created with at most k changes.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

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

Solution:

It can be defined that the largest maximum value among those possible is when you subtract the number of occurrences of the most frequent character within the window from the difference between the positions of the right and left pointers, and this result is equal to k.

• If it exceeds the k number of operations, you have no choice but to increment the left pointer by one, as in left += 1.

• Since it's a problem of finding the maximum length, it is better for the right to be as large as possible, and for the left to be as small as possible. Therefore, once a maximum value is reached, if the right pointer moves one step, the left pointer follows, and the max_len value does not change, so it can be omitted.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_len = 0
        counts = collections.Counter()  # Keeps track of the count of each character in the window
        left = right = 0

        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            # Find the count of the most frequent character in the current window
            max_char_n = counts.most_common(1)[0][1]
            
            # If the window size minus the count of the most frequent character is greater than k
            # it means we need more than k replacements, so we need to shrink the window
            if (right - left) - max_char_n > k:
                counts[s[left]] -= 1
                left += 1
            
        return right - left

counts.most_common(1)[0][1]

>>> counts
Counter({'A': 3, 'B': 2})

>>> counts.most_common()
[('A', 3), ('B', 2)]

>>> counts.most_common(1)
[('A', 3)]

>>> counts.most_common(1)[0]
('A', 3)

>>> counts.most_common(1)[0][1]
3