Algorithm
Problem Name: 424. Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
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.
Constraints:
1 <= s.length <= 105sconsists of only uppercase English letters.0 <= k <= s.length
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int characterReplacement(char* s, int k) {
int cnt[26] = { 0 };
int i, max, start, end;
max = start = end = 0;
while (s[end]) { // O(n) 3ms
i = s[end ++] - 'A';
cnt[i] ++;
max = max > cnt[i] ? max : cnt[i]; // longest length of single character
if (end - start > max + k) { // length of window exceeds the limit with all replacement
i = s[start ++] - 'A'; // shrink the window by advancing start pointer
cnt[i] --;
}
}
return end - start; // this is the biggest window
}
Input
s = "ABAB", k = 2
Output
4
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const characterReplacement = function(s, k) {
const len = s.length;
const count = Array(26).fill(0);
let start = 0,
maxCount = 0,
maxLength = 0;
const ca = "A".charCodeAt(0);
for (let end = 0; end < len; end++) {
maxCount = Math.max(maxCount, ++count[s.charCodeAt(end) - ca]);
if (end - start + 1 - maxCount > k) {
count[s.charCodeAt(start) - ca]--;
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
};
console.log(characterReplacement("ABAB", 2));
console.log(characterReplacement("AABABBA", 1));
Input
s = "ABAB", k = 2
Output
4
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
dic, start, end = {}, 0, 0
for end in range(1, len(s)+1):
if not s[end-1] in dic: dic[s[end-1]] = 1
else: dic[s[end-1]] += 1
if end-start-max(dic.values()) > k:
dic[s[start]] -= 1
start += 1
return end-start
Input
s = "AABABBA", k = 1
Output
4