Longest Substring with K Changes

You are given a string s and an integer k. You are allowed to change at most k characters in any substring of s. Your task is to find the length of the longest substring that can be obtained where all the characters are the same after performing at most k modifications.

For example, consider s = "ABAB" and k = 2. By changing both occurrences of A or B appropriately, you can convert the string into "AAAA" or "BBBB". Hence, the answer is 4.

The problem can be solved efficiently using the sliding window technique. Let \( n \) be the length of the string and let \( count[c] \) be the frequency of character \( c \) in the current window. If the length of the current window minus the maximum frequency within this window is greater than \( k \), then the window is invalid and must be adjusted.

Formula: Let the current window be represented by indices \( [l, r] \). Then, the condition for a valid window is:

\( (r - l + 1) - \max_{c}count[c] \le k \)

Your task is to output the length of the longest valid substring.

inputFormat

The input consists of two lines:

• The first line contains a string s consisting of uppercase English letters.
• The second line contains an integer k representing the maximum number of allowed changes.

outputFormat

Output a single integer denoting the length of the longest substring where all characters can be made the same with at most k changes.

## sample

ABAB
2

4