Longest Repeating Substring After Replacements

Languages

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

Examples

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