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

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.

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