Back to DSA
Longest Repeating Character Replacement
mediumA string of uppercase English letters and an integer k are given. You may change up to k characters in the string to any other uppercase letter. After making at most k replacements, what is the length of the longest substring where every character is the same?
Examples
Example 1:
Input:
s = "XYXY", k = 1Output:
3Explanation: Change one 'Y' to 'X' (or vice versa) to obtain a run of three identical characters, e.g., 'XXX' within 'XXXY'.
Example 2:
Input:
s = "AABABBA", k = 2Output:
5Explanation: Replace two B's to get 'AAAAABA' or similar. The longest uniform segment is 5.
Hints
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int maxCount = 0, maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
count[s.charAt(right) - 'A']++;
maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
while (right - left + 1 - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}Time complexity
O(n)Space complexity
O(1)