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) =
AABABBAk (int) =
1Returns (int)
4Example 2
Input
text (string) =
ABABk (int) =
2Returns (int)
4Example 3
Input
text (string) =
AAAAk (int) =
0Returns (int)
4Use 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 bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run