Given a string str consisting of uppercase English letters and an integer k, determine the length of the longest substring that can be formed where all characters are the same. A maximum of k character replacements can be made to achieve this.

A substring is any contiguous sequence of characters within a string. For example, the substrings of string abc are a, b, c, ab, bc, and abc. A substring is formed by selecting a starting and ending point without skipping characters in between.

Input

• str: string: A string
• k: An integer

Input: str = "ABCDE", k = 2
Output: 3
Explanation: Modify any two characters to match each other, resulting in a maximum length of 3. For instance, change 'B' and 'C' to 'A', transforming the string into 'AAADE'.

Input: str = "AAAA", k = 3
Output: 4
Explanation: All characters are already the same, so no changes needed, and the entire string forms the longest substring.

Input: str = "AABAA", k = 2
Output: 5
Explanation: By replacing 'B' with 'A', the string becomes 'AAAAA', which is the longest substring of identical characters.

Constraints

• 1 <= str.length <= 10,000
• str contains only uppercase English letters