Longest Substring with Same Letters After k Modifications

Given a string s and an integer k, you are allowed to perform at most k modifications on s. In each modification, you can change any character to any other character. Your task is to determine the length of the longest substring that can be transformed into a string with identical characters using no more than k modifications.

The problem can be formulated as follows:

Find the maximum length L such that there is a substring of s of length L where the number of characters that are not the same as the most frequent character is at most k.

This condition can be written in LaTeX as:

$$\text{substring length} - \max_{c \in \Sigma}(\text{frequency}(c) ) \le k$$

Examples:

• Input: s = "aabccbb", k = 2   →  Output: 5
• Input: s = "abbcb", k = 1   →  Output: 4
• Input: s = "abacaba", k = 0   →  Output: 1

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains the string s (which may be empty).
2. The second line contains the integer k, representing the maximum number of allowed modifications.

outputFormat

Output a single integer to stdout representing the length of the longest substring that can be transformed into a string with all identical characters with at most k modifications.

## sample

aabccbb
2

5