1. Longest Repeating Character Replacement (LeetCode)
Model answer
The task
Find the length of the longest substring that can be made entirely of one repeated character by changing at most k characters.
Key idea
Use a sliding window and track the most frequent character in it. The number of replacements needed is the window length minus that frequency, so shrink the window whenever this exceeds k.
Approach
- Keep a frequency count for characters in the current window.
- Expand the right edge one character at a time and update the highest frequency seen.
- If the window would need more than
kreplacements, move its left edge forward. - Record the largest window length.
The maximum frequency is intentionally not recomputed when the window shrinks. It may be stale, but this still gives the correct maximum length: the window only stays large when its length is supported by a frequency seen in a previously valid window.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = {}
left = 0
max_frequency = 0
longest = 0
for right, char in enumerate(s):
counts[char] = counts.get(char, 0) + 1
max_frequency = max(max_frequency, counts[char])
# Shrink until the window can be made uniform with at most k changes.
if (right - left + 1) - max_frequency > k:
counts[s[left]] -= 1
left += 1
longest = max(longest, right - left + 1)
return longest
Complexity:
- Time: O(n), where n is the string length; each pointer moves at most n times.
- Space: O(1), since the frequency map has at most 26 entries for uppercase English letters.
Common follow-ups
- What if the string can contain arbitrary Unicode characters? Use a dictionary for counts; the space then depends on the number of distinct characters.
- Can the method return the substring as well as its length? Store the best window’s start and end indices whenever the best length increases.
- What if replacements have different costs? Track the minimum cost to make the window uniform and shrink while that cost exceeds the budget.