Longest Substring with At Least K Repeating Characters

You are given a string s consisting of lowercase English letters and an integer k. Find the length of the longest substring of s such that the frequency of each character in the substring is at least k.

In other words, for any substring sub considered valid, for every character c in sub, the frequency f(c) must satisfy the inequality:

$$f(c) \ge k$$

If there is no such substring, output 0.

Example:

Input:
aaabbcc
3
Output:
3

</p>

The substring "aaa" is the longest valid substring since each character in it appears at least 3 times.

inputFormat

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

• The first line contains a non-empty string s (only lowercase English letters).
• The second line contains an integer k representing the minimum frequency requirement.

outputFormat

Output to standard output (stdout) a single integer — the length of the longest substring of s in which every character appears at least k times. If no such substring exists, output 0.

## sample

aaabbcc
3

3