Smallest Substring with K Distinct Characters

You are given a string s and an integer K. Your task is to find the length of the smallest contiguous substring of s that contains exactly K distinct characters. If no such substring exists, output -1.

More formally, for a given string s and a positive integer K, find the minimum length L such that there exists a substring s[i...j] with j - i + 1 = L where the number of distinct characters in s[i...j] is exactly K. In mathematical notation, if we let \(\mathcal{D}(s[i\ldots j])\) be the set of distinct characters in that substring, then we need:

[ \min{ j-i+1 \mid |\mathcal{D}(s[i\ldots j])| = K } ]

If no such substring exists, you must output -1.

inputFormat

The input is read from standard input (stdin) and consists of several datasets. Each dataset is described by two consecutive lines:

• The first line is the string s (consisting of alphabetic characters or others).
• The second line is an integer K indicating the required number of distinct characters.

The input terminates when a line containing only the character 0 is encountered. This line should not be processed.

outputFormat

For each dataset, print the length of the smallest substring that contains exactly K distinct characters. If no valid substring exists, print -1. Each result should be printed on a separate line to standard output (stdout).

## sample

abcada
3
aaaaa
2
abac
5
0

3
-1
-1

</p>