# 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%28n%29-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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/two_pointers/longest-repeating-character-replacement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.