Longest Repeating Character Replacement - Leetcode Solution

The Longest Repeating Character Replacement problem on leetcode asks us to find the longest substring in a given string s, where we can replace at most k characters in the substring such that all the characters in the substring are the same.

To find the solution, we can use a sliding window approach where we maintain a window of characters and keep track of the maximum repeating character within the window. If the number of non-repeating characters within the window exceeds k, we decrement the size of the window by moving the left pointer, otherwise, we increment the size of the window by moving the right pointer.

Algorithm:

1. Initialize a hashmap to keep track of the frequency of each character in the given string.
2. Define pointers, left and right, to denote the limits of the window.
3. Define a variable, max_char_count, to keep track of the maximum repeating count of any character within the window.
4. Define a variable, max_length, to keep track of the maximum length of a substring that can be formed within the window.
5. Move the right pointer forward until the window has at most k non-repeating characters.
6. Update the max_length if the current window has a longer substring than previous windows.
7. Move the left pointer forward and decrement the frequency of the left character in the hashmap.
8. If the left character had the maximum repeating count, recalculate the max_char_count.
9. Repeat steps 5-8 until the right pointer goes beyond the end of the string.
10. Return max_length as the final result.

Here is the Python code:

def characterReplacement(s: str, k: int) -> int:
    freq_map = {}
    left = right = max_char_count = max_len = 0
    
    while right < len(s):
        freq_map[s[right]] = freq_map.get(s[right], 0) + 1
        max_char_count = max(max_char_count, freq_map[s[right]])
        
        if (right-left+1) - max_char_count > k:
            freq_map[s[left]] -= 1
            left += 1
        
        max_len = max(max_len, right-left+1)
        right += 1
    
    return max_len

The time complexity of the above algorithm is O(n) and the space complexity is O(1) since the size of the hashmap is at most 26 (for all possible lowercase English alphabets).

1