Longest Substring with K Modifications

You are given a string s consisting of lowercase English letters and an integer k. You are allowed to perform at most k character modifications on s. A modification means changing any character to any other character.

Your task is to determine the length of the longest substring that can be obtained such that all its characters are identical after performing at most k modifications.

The problem can be mathematically described as finding the maximum length L for which there exists a substring s[i...j] with $$(j - i + 1) - \max_{c \in \{a,...,z\}}(\text{count}(c)) \le k, $$

where (\text{count}(c)) represents the frequency of character c in the substring. Use this relation to determine the maximum achievable substring length.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains the string s (a sequence of lowercase English letters).
2. The second line contains an integer k, which is the maximum number of allowed modifications.

outputFormat

Output a single integer representing the length of the longest substring in which all characters are the same after at most k modifications. The output should be written to standard output (stdout).

aabccbb
1

3