424. Longest Repeating Character Replacement (Medium)
https://leetcode.com/problems/longest-repeating-character-replacement/
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.
Solutions
class Solution {
// To get longest repeating character replacement, we need to sort out substrings that
// consists of k + 1 unique characters. Then replace those of low frequence.
public int characterReplacement(String s, int k) {
Set<Character> letters = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
letters.add(s.charAt(i));
}
int max = 0;
for (Character c : letters) {
// count for current character
int count1 = 0;
// count for other character
int count2 = 0;
// left and right pointer
int lptr = 0;
int rptr = 0;
while(true) {
if (s.charAt(rptr) == c) {
count1++;
} else {
count2++;
}
// update the max len of repeating characters if possible
if (count2 == k && count1 + count2 > max) {
max = count1 + count2;
}
// It's allowed to replace only at most k elements. Once exceeds this limit,
// prune the window from left, remove the head char.
while(count2 > k) {
if (s.charAt(lptr) == c) {
count1--;
} else {
count2--;
}
lptr++;
}
// rptr must not overstep the boundary of s
if (rptr == s.length()-1) {
// before break the loop, check out the last subsequence
if (count1 + count2 > max) {
max = count1 + count2;
}
break;
}
rptr++;
}
}
return max;
}
}