Longest Repeating Character Replacement

Medium~25 min

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Examples

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two "A"s with two "B"s or vice versa. The entire string becomes uniform.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Replace the one "B" in the middle (index 2) to get "AAAAABA", giving a substring "AAAA" of length 4.

Constraints

1 <= s.length <= 10^5
s consists of only uppercase English letters
0 <= k <= s.length
Expected time complexity: O(n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run