# 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++) {
}

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;
}
}
``````