Longest Repeating Character Replacement

medium

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "ABAB", k = 2

Expected Output

4

Explanation: Replace the two A's with two B's, or vice versa.

Input

s = "AABABBA", k = 1

Expected Output

4

Explanation: Replace the one A in the middle with B to form "AABBBBA", whose longest repeating substring is "BBBB".

Constraints

1 <= s.length <= 10^5
s consists of only uppercase English letters.
0 <= k <= s.length

Hints

Hint 1 — click to reveal

A window is valid when (window length - count of its most frequent letter) <= k.

Hint 2 — click to reveal

That difference is exactly the number of characters you would have to replace.

Java Compiler