# 424. Longest Repeating Character Replacement
Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.
In one operation, you can choose any character of the string and change it to any other uppercase English character.
Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.
Note: Both the string's length and k will 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.
# Solution
Approach 1: sliding window (with greedy window length).
# Code (Python)
Approach 1:
import collections
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if k >= len(s):
return len(s)
if len(s) <= 1:
return len(s)
l = 0
max_freq_in_window = 1
max_len = 1
freqs = collections.defaultdict(int)
for r in range(len(s)):
freqs[s[r]] += 1
# this means increased running time
#while r - l + 1 - max(freqs.values()) > k:
# alternatively, this reduces time to O(N)
# it works because we want to find the global best, so a local max freq can be ignored. e.g. BBB(ABAA), max_freq_in_window = 4
# More explanation at https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91271/Java-12-lines-O(n)-sliding-window-solution-with-explanation "Since we are only interested in the longest valid substring, our sliding windows need not shrink, even if a window may cover an invalid substring. We either grow the window by appending one char on the right, or shift the whole window to the right by one. And we only grow the window when the count of the new char exceeds the historical max count (from a previous window that covers a valid substring). That is, we do not need the accurate max count of the current window; we only care if the max count exceeds the historical max count; and that can only happen because of the new char."
max_freq_in_window = max(max_freq_in_window, freqs[s[r]])
while r - l + 1 - max_freq_in_window > k:
l += 1
freqs[s[l - 1]] -= 1
max_len = max(max_len, r - l + 1)
return max_len
# Code (C++)
Approach 1:
Approach 2: