Longest Repeating Character Replacement

Question statment

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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 achive this answer too.

Solution

For this one, it's important to not overthink it. The question is asking us to replace k character but actually it's just looking for the longest length that has most k character difference.

This can simply calculate using this formula:
$$ currentLength - mostFrequentCharacterLength \leq k$$
If this condition is satisfied, we will calculate it to store the maxLength.

For example, given a string:

s = AABBAABBACAB, k = 2

at 1 certain point

  v
AABBAABBACAB
       ^

Following the formula, we know that this string BBAABB satisfies the condition:

• $currentLength$: 6
• $mostFrequentCharacterLength$ : 4 (4 B's)

And 7-4 <= 2 therefore the string satisfies that we can replace k character to make the string valid.

Using the same concept, we can solve this with Fast and Slow pointers. Creating a window.

• We increment fast for every string we go through
• We increment slow when we have an invalid window. Therefore, we want to decrease the size of our window to reduce $currentLength$ which potentially brings it to be smaller than k
  • When increment slow, we also remove the previous letter from the count, therefore also potentially lessen $mostFrequentCharacterLength$

Implementation

class App:
    def characterReplacement(self, s: str, k: int) -> int: 
        if len(s) <= k: return len(s)
        frequency = Counter()
        slow, fast = 0, 0
        maxLength = 0
        
        while (fast < len(s)):
            frequency[s[fast]] += 1
            currentStringLength = fast - slow + 1
            
            while currentStringLength - self.getMaxFrequency(frequency) > k:
                frequency[s[slow]] -= 1
                slow += 1
                currentStringLength = fast - slow + 1

            maxLength = max(maxLength, currentStringLength)
            fast += 1

        return maxLength
    
    def getMaxFrequency(self, frequency: Dict[str, int]) -> int:
        return max(frequency.values())

Time Complexity: $O(26n)$

• getMaxFrequency() is $O(26)$ since there are 26 characters in the alphabets
  Space Complexity: $O(26)$
• to store the frequency array