You are given a string s and an integer k. You can choose any character and change it to any uppercase English letter up to k times. Return the length of the longest substring containing the same letter after performing at most k replacements.

Example 1:

Input: ABAB
k: 2
Output: 4

Example 2:

Input: AABABBA
k: 1
Output: 4

Constraints:

• 1 ≤ s.length ≤ 10⁵
• s consists of uppercase English letters
• 0 ≤ k ≤ s.length

Input format: First line: string s. Second line: integer k.

Output format: Length of longest valid substring.