Shortest Substring with (k) Unique Characters

Given a string \(s\) and an integer \(k\), find the length of the shortest contiguous substring of \(s\) that contains at least \(k\) unique characters. If no such substring exists, output -1.

Example: For \(s = \texttt{abcba}\) and \(k = 3\), one valid shortest substring is \(\texttt{bcb}\) with length 3.

The problem can be solved using a sliding window technique. As you traverse the string, maintain a current window and update your answer as soon as the window contains at least \(k\) distinct characters. Use appropriate data structures to count the occurrence of characters.

inputFormat

The input is provided 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 \(k\), representing the minimum number of unique characters required in the substring.

You may assume that \(0 \leq k \leq |s|\).

outputFormat

Output a single integer to stdout, which is the length of the shortest substring of \(s\) that contains at least \(k\) unique characters. If no such substring exists, output -1.

abcba
3

3