Smallest Substring with at Least N Distinct Characters

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

More formally, let S be a substring of s. You need to find the minimum length of S such that

$$|\{ c : c \in S \}| \geq n$$

If it is impossible to have a substring with at least n distinct characters, output -1.

Examples

• Input: s = "abcba", n = 3, Output: 3
• Input: s = "aaaaaa", n = 2, Output: -1
• Input: s = "a", n = 1, Output: 1
• Input: s = "abcdef", n = 4, Output: 4

inputFormat

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

1. The first line contains the string s consisting of lowercase English letters.
2. The second line contains an integer n, which is the minimum number of distinct characters required in the substring.

outputFormat

Output a single integer representing the length of the smallest substring of s that contains at least n distinct characters. If there is no such substring, output -1.

## sample

abcba
3

3