Array String Hash Map Sliding Window
Proficient Level

Implement the longestRepeatingCharReplacement method that returns the longest substring length after replacing at most k characters.

The input contains a string text and an integer k. You may replace at most k characters in a substring.

Your task is to find the length of the longest substring that can be changed into a string containing only one repeated character.

For example, in AABABBA with k = 1, one valid longest length is 4.

Example 1
Input:
text (string) = AABABBA
k (int) = 1
Return:
(int) 4
Example 2
Input:
text (string) = ABAB
k (int) = 2
Return:
(int) 4
Example 3
Input:
text (string) = AAAA
k (int) = 0
Return:
(int) 4

Use a sliding window and track the most frequent character inside the current window.

For a window to become all one character, every character except the most frequent one must be replaced. Therefore, the number of replacements needed is windowLength - maxFrequency.

If replacements needed are more than k, shrink the window from the left. Otherwise, update the best length.

Pseudocode:

function longestRepeatingCharReplacement(text, k):
    left = 0
    best = 0
    maxFrequency = 0
    frequency = empty map
    for right from 0 to length of text - 1:
        add text[right] to frequency
        maxFrequency = maximum(maxFrequency, frequency[text[right]])
        while (right - left + 1) - maxFrequency > k:
            decrease frequency of text[left]
            left++
        best = maximum(best, right - left + 1)
    return best
Run your code to see the result.