You are given a string s of uppercase English letters and an integer k. You may change at most k characters of s into any other uppercase letter. Return the length of the longest substring that can be made of a single repeated letter after these changes.
As to B (or both Bs to A) to get four equal letters.A at index 3 to get "BBBB" from index 3 to 6.- 1 <= s.length <= 10^5
- `s` has only uppercase English letters
- 0 <= k <= s.length
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking every substring costs O(n^2) windows. For any window, the cheapest fix keeps its most common letter and changes the rest, so it needs length - maxCount changes. Slide a window with letter counts: extend right, and if the window needs more than k changes, move left by one. The window never shrinks, so its size always equals the best answer found so far. maxCount may become stale (too high) after moving left, but that is fine: a stale value can only stop the window from growing, and the answer only improves when a real higher count appears.
Algorithm
- Keep
count[26],left = 0,maxCount = 0. - For each
right, increasecount[s[right]]and setmaxCount = max(maxCount, count[s[right]]). - If
(right - left + 1) - maxCount > k, decreasecount[s[left]]and moveleftright by one. - The answer is the final window length
n - left.
O(n)Space: O(1), 26 countersmaxCount does not need to be recomputed when the window slides. Be ready to explain that the answer only grows when some letter reaches a new higher count.class Solution: def characterReplacement(self, s: str, k: int) -> int: count = [0] * 26 left = max_count = 0 for right, ch in enumerate(s): c = ord(ch) - ord('A') count[c] += 1 max_count = max(max_count, count[c]) # Too many letters to change: slide the window by one. if right - left + 1 - max_count > k: count[ord(s[left]) - ord('A')] -= 1 left += 1 return len(s) - left # the window never shrinks