You are given a string
s consisting of uppercase English letters and an integer k. You can choose any character in the string and change it to any other uppercase English letter at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.Example
s = "AABABBA", k = 1
Output: 4
The substring "AABA" (indices 0-3) has 3 A’s and 1 B. Replacing that single B with A gives "AAAA", a string of 4 repeating characters, using exactly 1 replacement.
Use a sliding window and track the frequency of each character inside it. The key insight is that a window is valid if (window size - count of most frequent character) <= k, because that difference is the number of characters you'd need to replace. When the window becomes invalid, shrink from the left.
Why this works
In any window, you only need to replace the characters that are NOT the most frequent one. So the number of replacements needed is (window size - count of most frequent character). If that exceeds k, the window is too big and you shrink from the left. This lets you find the longest valid window in one pass.
Step by step
- Expand the window — move the right pointer forward and update the frequency count for the new character.
- Track the most frequent character — this tells you the fewest replacements needed to make the whole window uniform.
- Shrink if invalid — if (window size - max frequency) > k, you need more than k replacements, so move left inward.
- Record the best — after each adjustment, the current window is valid, so compare its size to the max seen.
Time: O(n)
Space: O(1)
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxFreq = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
count[s.charAt(right) - 'A']++;
maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
while ((right - left + 1) - maxFreq > k) { // too many chars need replacing
count[s.charAt(left) - 'A']--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1); // valid window, track best
}
return maxLen;
}
}
class Solution {
public:
int characterReplacement(string s, int k) {
int count[26] = {0};
int left = 0, maxFreq = 0, maxLen = 0;
for (int right = 0; right < s.size(); right++) {
count[s[right] - 'A']++;
maxFreq = max(maxFreq, count[s[right] - 'A']);
while ((right - left + 1) - maxFreq > k) { // too many chars need replacing
count[s[left] - 'A']--;
left++;
}
maxLen = max(maxLen, right - left + 1); // valid window, track best
}
return maxLen;
}
};
def characterReplacement(s: str, k: int) -> int:
count = [0] * 26
left = 0
max_freq = 0
max_len = 0
for right in range(len(s)):
count[ord(s[right]) - ord('A')] += 1
max_freq = max(max_freq, count[ord(s[right]) - ord('A')])
while (right - left + 1) - max_freq > k: # too many chars need replacing
count[ord(s[left]) - ord('A')] -= 1
left += 1
max_len = max(max_len, right - left + 1) # valid window, track best
return max_len