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，这一题其实会容易理解得多。

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

参考这篇@chrislzm的补充回答的解释：

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

Whenend-start+1-maxCount== 0, then then the window is filled with only one character Whenend-start+1-maxCount> 0, then we have characters in the window that are NOT the character that occurs the most.end-start+1-maxCountis 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 whenend - start + 1 - maxCount > k, then there are more characters in the window than we can replace, and we need to shrink the window.

maxCountmay 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

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

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