# Longest Repeating Character Replacement

**Medium**

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 andkwill 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.
```

## Analysis

如果遇见过[Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/)，这一题其实会容易理解得多。

这题的难度应该不在 340.[Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) 之下，在那一题的基础之上，这一题，其实也要维护一个滑动窗口，不过移动左边慢指针的条件变得更复杂了。340需要维护大小不超过k的hashmap，保证窗口中元素的种类最多为k个，而424这题则是要保持窗口中非重复元素的个数少于等于k，以便在k次replacement操作之内能够变化这一段window成为连续的repeating letters。

参考这篇[@chrislzm](https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91271/Java-12-lines-O\(n\)-sliding-window-solution-with-explanation/137008)的补充回答的解释：

`end - start + 1` = size of the current window

`maxCount` = largest count of a single, unique character in the current window

The main equation is:`end - start + 1 - maxCount`

When`end-start+1-maxCount`== 0, then then the window is filled with only one character\
When`end-start+1-maxCount`> 0, then we have characters in the window that are NOT the character that occurs the most.`end-start+1-maxCount`is equal to exactly the # of characters that are NOT the character that occurs the most in that window.

We are allowed to have at most k replacements in the window, so when`end - start + 1 - maxCount > k`, then there are more characters in the window than we can replace, and we need to shrink the window.

`maxCount`**may be invalid at some points, but this doesn't matter, because it was valid earlier in the string, and all that matters is finding the max window that occurred *****anywhere***** in the string**. Additionally, it will expand \_**if and only if** \_enough repeating characters appear in the window to make it expand. So whenever it expands, it's a valid expansion.

这里要注意的是`maxCount` 其实指的是在遍历过的window中最大的重复元素计数，因此有些时候当window缩小时，这个maxCount不代表当前窗口中的最多的重复元素计数。但是最终结果是

## Solution

**Sliding Window - Two Pointers** - (9 ms, faster than 63.21%)

O(n) time, O(k) space

```java
class Solution {
    public int characterReplacement(String s, int k) {

        int[] count = new int[26];
        int maxCount = 0; 
        int maxLength = 0;

        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A'] += 1;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            while (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A'] -= 1;
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```

Two Pointer - Another implementation by [@star1993](https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91286/Java-Sliding-Window-Easy-to-Understand)

```java
public class Solution {
    public int characterReplacement(String s, int k) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int max = 0;
        int[] ch = new int[26];
        char[] str = s.toCharArray();
        for(int i=0, j=0; i<s.length(); i++){
            while(j < s.length()){
                ch[str[j] - 'A']++;
                if(count(ch) > k){  //If exceed k, break
                    ch[str[j] - 'A']--;
                    break;
                }
                j++;
            }
            max = Math.max(max, j-i);
            ch[str[i] - 'A']--;
        }
        return max;
    }
    //Count the number of character that is different to the longest character
    public int count(int[] ch){
        int max = 0;
        int sum = 0;
        for(int val:ch){
            sum += val;
            max = Math.max(max, val);
        }
        return sum - max;
    }
}
```

## Reference

<https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91286/Java-Sliding-Window-Easy-to-Understand>