Longest Repeating Character Replacement


Medium

Given a string s and an integer k. Choose any character of the string and change it to any other uppercase English character. You can do this at most k times.

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

 

Man needs difficulties in life because they are necessary to enjoy the success. - A. P. J. Abdul Kalam

Example

Input: s = "ABAB", k = 2 Output: 4

Explanation: Replace the two 'A's with two 'B's or two 'B' with two 'A'. The resultant string will be “AAAA” or “BBBB”. So the length longest substring with same letters will be 4 in any case.

 

Input: s = "AABABBA", k = 1 Output: 4

Explanation: Replace 'A' in the middle of string with 'B' to get "AABBBBA".

The substring "BBBB" has the longest repeating letters, which is 4.