← 返回 microsoft 的题目列表Shortest Subarray (Substring) Length With At Least K Distinct Characters
类型：online_judge
Problem
Given a string s and an integer K, among all contiguous substrings of s, find one that contains at least K distinct characters and return its minimum length.
If no substring satisfies “at least K distinct characters”, return -1.
Input
One line: string s
One line: integer K
Output
An integer: the minimum substring length satisfying the condition; output -1 if none exists.
Constraints (suggested)
1 <= len(s) <= 2 * 10^5
1 <= K <= alphabet size
Example
Example 1
Input:
s = "abac"
K = 3
Output: 3
Explanation: the shortest valid substring is "bac" (distinct chars: b, a, c), length 3.
Example 2
Input:
s = "aaaa"
K = 2
Output: -1
Example
Input
abac
3
Output
3