Longest Repeating Character Replacement
Medium · Sliding Window · Hash Table · String · Sliding Window
Problem
s is a string of uppercase English letters. You may change at most k of its characters, each to any uppercase letter. Return the length of the longest substring made of one repeated letter that you can get this way.
You do not have to use all k changes, and the run can be made of any letter, not only the most common one in s. A window can be made uniform exactly when its length minus the count of its most common letter is at most k: keep that letter and change the rest.
Examples
Input: s = "ABAB", k = 2 Output: 4
Change both As to B, or both Bs to A: the whole string becomes one letter.
Input: s = "AABABBA", k = 1 Output: 4
Change the A in the middle of BABB to get BBBB. No window of 5 has only one letter out of place.
Constraints
- 1 <= len(s) <= 10^5
- s consists of uppercase English letters
- 0 <= k <= len(s)
Approaches
- Check every substring — time O(n²), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
