All problems

Longest Repeating Character Replacement

Medium · sliding window

You are given a string s made of uppercase English letters and a whole number k. You may change at most k characters of s, and each changed character can become any uppercase letter you like.

After making your changes, look for the longest substring (a run of neighbouring characters) in which every character is the same letter. Return the length of the longest such run that you can create.

You are free to make fewer than k changes, or none at all. The string is never empty, so the answer is always at least 1.

Examples

Example 1

Input: s = "ABAB", k = 2

Output: 4

Change both B characters to A (or both A characters to B) and the whole string is one letter.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Change the B in "AABA" to A to get "AAAA". No run of length 5 can be built with a single change.

Example 3

Input: s = "ABCDE", k = 0

Output: 1

No changes are allowed, and no letter appears twice in a row.

Constraints

• 1 <= len(s) <= 10^5
• s consists of uppercase English letters
• 0 <= k <= len(s)