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.

Formally, if we denote by \( s[i \ldots j] \) a substring of s and \( |\cdot| \) the length of a substring, you are to compute \[ \max \{ |s[i \ldots j]| : s[i \ldots j] \text{ contains at most } k \text{ distinct characters} \}. \]

If k is 0 or the string is empty, the answer is 0.

Note: a substring is a contiguous sequence of characters in a string.

inputFormat

The input consists of two lines:

• The first line contains a string s. This string may be empty.
• The second line contains an integer k.

Both inputs are read from stdin.

outputFormat

Output a single integer that represents the length of the longest substring of s containing at most k distinct characters.

The result should be printed to stdout.

## sample

eceba
2

3