Longest Repeating Character Replacement

Sliding Window

Problem

Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement.

For 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.

Thought Process

• We are going to keep track of how many distinct characters we have within our window that are not equal to character with maxRepeatingCount and compare this distinct character count with 'K'

  • We are comparing the distinct character count to 'K' because the distinct character count will determine if we can do 'K' replacements

• We will use a dictionary to keep track of the characters to their count so we can get the character with maxRepeatingCount

• We shrink our sliding window when the number of distinct characters not equal to our maxRepeatCount character surpasses 'K' because this means we have more distinct characters than the number of replacement operations that are allowed

Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        maxLen = 0
        maxCharCount = 0
        freq = {}
        start = 0
        
        for i in range(len(s)):
            if s[i] not in freq:
                freq[s[i]] = 1
            elif s[i] in freq:
                freq[s[i]]+=1
            maxCharCount = max(maxCharCount, freq[s[i]])
            
            if (i - start + 1 - maxCharCount) > k:
                freq[s[start]]-=1
                start+=1
            
            maxLen = max(maxLen, i - start + 1)
            
        return maxLen
        

Key Points

• Using a dictionary to count the frequency of each letter

• We are keeping track of the count of the maximum repeating letter in any window with a maxRepeatChar variable

• We will know when there are more characters than allowed operations when we apply $windowEnd-windowStart+1-maxRepeatChar$. When this is the case, we will shrink our window.

  • maxRepeatChar is the character with the highest frequency within the window

• While shrinking the window, we don't need to update maxRepeatChar. The reason is because in any window, since we have to replace all the remaining letters to get the longest substring having same letter, we can't get a better answer from any other window even though all occurences in the string of the letter with frequency maxRepeatChar is not in the current window

Time Complexity

• Time: $O(n)$

• Space: $O(1)$ because as we expect only the lower case letters in the input string, we can conclude that the space complexity will be $O(26)$ to store each letter’s frequency in the HashMap, which is asymptotically equal to $O(1)$ .