Longest Repeating Character Replacement

Find the longest substring you can make with one character by replacing at most k characters.

sliding-window strings hash-map two-pointers

You are given a string `s` consisting of uppercase English letters and an integer `k`. You may choose any substring and replace at most `k` characters with any uppercase letter so that all characters in the substring become the same letter. Return the length of the longest substring you can achieve.

Implement the function `character_replacement(s: str, k: int) -> int` that returns the maximum possible length.

For example, with `s = "AABABBA"` and `k = 1`, you can replace the middle 'B' with 'A' to get `"AABAABA"`? Actually, consider the substring `"AABABBA"` indices 0..4 = `"AABAB"`. Replace the 'B' at index 3 with 'A' to get `"AAAAA"`? Wait, indices 0..4 are `A A B A B`, with two Bs; replacing both Bs would need k=2. With k=1, the longest is 4: substring `"AABA"` (indices 0..3) replace the 'B' with 'A' to get `"AAAA"`, or `"ABBA"` (indices 2..5) replace the 'A' with 'B' to get `"BBBB"`, length 4. So the answer is 4.

Constraints:
- `0 <= len(s) <= 10^5`
- `s` consists only of uppercase English letters.
- `0 <= k <= len(s)`

Your solution should run in O(n) time and O(1) extra space (or O(26) space).

Constraints

Input constraints:
- 0 <= len(s) <= 10^5
- s contains only uppercase English letters (A-Z).
- 0 <= k <= len(s)
Complexity: Expected O(n) time and O(1) space.

Example

>>> character_replacement("ABAB", 2)
4
>>> character_replacement("AABABBA", 1)
4
>>> character_replacement("AAAA", 2)
4
>>> character_replacement("", 0)
0

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a sliding window with two pointers. The window is valid if the number of characters to replace (window length minus the most frequent character count) is at most k.

As you expand the right pointer, update the frequency of the new character. Then, while the window is invalid, shrink from the left and update frequencies.

Track the max window size seen. The answer is the maximum window length ever achieved.

You don't need to shrink one by one; you can also just keep the window size valid by shifting left when invalid, but careful with max frequency tracking.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.