Character Replacement Window

Find the longest substring you can make by changing at most k characters.

sliding-window two-pointers strings hashmap

Write a function `longest_repeating_char_replacement(s, k)` that takes a string `s` (containing only uppercase English letters) and an integer `k` (non-negative). It returns the length of the longest substring that can be transformed into a string consisting of a single repeated character by changing at most `k` characters anywhere in the substring.

You may change any character to any other character. The substring must be contiguous. If `s` is empty, return 0.

Constraints

- `0 <= len(s) <= 100000`
- `0 <= k <= len(s)`
- `s` consists of uppercase English letters only.

Time complexity must be O(n) or O(n * 26), where n = len(s). Space complexity O(1) or O(26).

Example

```python
>>> longest_repeating_char_replacement("ABAB", 2)
4
>>> longest_repeating_char_replacement("AABABBA", 1)
4
>>> longest_repeating_char_replacement("AAAA", 2)
4
>>> longest_repeating_char_replacement("", 0)
0
```

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about a sliding window. For any window, the minimal changes needed = window length - frequency of the most common character in that window.

Expand the right pointer. If the window is invalid, shrink from the left until it becomes valid again.

You only need to track the frequencies of characters inside the current window and the maximum frequency seen so far.

Test Results

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