Longest Repeating Character Replacement

Longest Repeating Character Replacement

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 letter. 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 'B's or vice versa. The entire string becomes "BBBB" or "AAAA".

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the 'B' at index 3 with 'A'. The substring "AABA" has length 4.
Alternatively, replace the 'A' at index 4 to get "AABBBBA" → substring "BBBB" of length 4.

Example 3:

Input: s = "AAAA", k = 0
Output: 4
Explanation: No replacements needed. The entire string is already the same character.

Constraints

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

Expected Complexity

• Time: O(n)
• Space: O(1). at most 26 letters in the frequency map