Longest Substring with At Most K Distinct Characters

You are given a string s and an integer k. Your task is to find the length of the longest substring of s that contains at most k distinct characters.

More formally, if we denote the number of distinct characters in a substring s[i...j] by \(d(s[i...j])\), you need to compute:

[ \max_{0 \le i \le j < n ;\text{and}; d(s[i...j]) \le k} (j - i + 1) ]

It is guaranteed that the input string contains only ASCII characters. Use an efficient sliding window technique to solve this problem!

Example: For s = "araaci" and k = 2, the longest substring with at most 2 distinct characters is "araa" with length 4.

inputFormat

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

• The first line contains the string s.
• The second line contains an integer k.

It is guaranteed that s contains only ASCII characters.

outputFormat

Output the length of the longest substring of s that contains at most k distinct characters. The answer should be printed to standard output (stdout).

## sample

araaci
2

4