Longest Substring with At Most K Replacements

You are given an integer k and a string s. Your task is to find the length of the longest substring of s which can be transformed into a substring with all identical characters by replacing at most k characters.

In other words, you may choose at most k characters in a contiguous segment of s and change them to any other character in order to make the entire substring consist of the same character. The answer is the maximum possible length of such a substring.

The sliding window algorithm is typically used to solve this problem. For a window from index l to r, let max_freq be the count of the most frequent character in that window. The window is valid if: $$ (r - l + 1) - max_{freq} \le k $$ Otherwise, the window is shrunk from the left.

inputFormat

The input is provided via standard input (stdin) and consists of two lines. The first line contains a single integer k representing the maximum number of allowed replacements. The second line contains the string s.

outputFormat

Output a single integer which is the length of the longest substring that can be achieved after performing at most k replacements. The output should be sent to standard output (stdout).

2
ABAB

4