Longest Repeating Character Replacement
Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring does not exceed k replacements. You can replace any character with any other character.
Constraints:
- 1 <= s.length <= 10^5
- 0 <= k <= 10^5
- s consists of only uppercase English letters
Examples:
Input: "ABAB" and k = 2
Output: 4
Explanation: The longest substring is "ABAB" where we can replace two 'B's with two 'A's.
Solutions
Sliding Window with Frequency Count
We use a sliding window approach with two pointers, left and right. We maintain a frequency count of characters in the current window. We expand the window to the right and update the frequency count. If the window size exceeds the maximum allowed replacements, we shrink the window from the left. We keep track of the maximum length of the substring that can be formed with at most k replacements.
int characterReplacement(string s, int k) {
int left = 0, maxLen = 0, maxCount = 0;
int count[26] = {
0}
;
for (int right = 0;
right < s.size();
right++) {
count[s[right] - 'A']++;
maxCount = max(maxCount, count[s[right] - 'A']);
if (right - left + 1 - maxCount > k) {
count[s[left] - 'A']--;
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}Follow-up:
What if we need to find the longest substring with at most k replacements and the substring must contain at least one 'A'?
