Problem
You are given a string s and an integer k. You can replace at most k characters in the string with any uppercase English letter.Return the length of the longest substring that can be transformed into a string containing only the same character after performing at most k replacements.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "AABABBA"
k = 1 Output
4 Solution
This solution uses the Sliding Window technique along with a frequency array to keep track of how many times each character appears in the current window.As the window expands, the frequency of the newly added character is updated, and the frequency of the most common character in the current window is maintained.
The number of characters that need to be replaced is calculated as windowSize - maxFrequency. This works because all other characters in the window must be changed to match the most frequent character.
If the number of required replacements becomes greater than k, the window is no longer valid. The left side of the window is then moved forward, reducing the frequency of the character that leaves the window, until the window becomes valid again.
Throughout the traversal, we keep track of the largest valid window. Its size is the length of the longest substring that can be formed after replacing at most k characters.
public int characterReplacement(String s, int k) {
int[] freq = new int[26];
int left = 0;
int maxFreq = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
int index = s.charAt(right) - 'A';
freq[index]++;
maxFreq = Math.max(maxFreq, freq[index]);
while ((right - left + 1) - maxFreq > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
Complexity
The algorithm scans the string only once using a sliding window. Each character is added to and removed from the window at most once, resulting in an overall time complexity ofO(n). The frequency array has a fixed size of 26, so the extra space complexity is
O(1).