Find shortest substring with N unique characters

You are given a string s and an integer n.

Find the shortest contiguous substring of s that contains exactly n distinct characters.

If there is no such substring, return an empty string (or -1, depending on how you choose to represent "not found"). If multiple substrings have the same minimal length, returning any one of them is acceptable.

Requirements

• Input:
• s: a non-empty string composed of ASCII letters (you may assume lowercase English letters if you want to simplify).
• n: an integer, 1 <= n <= 26 (assuming lowercase letters) and n <= number of distinct characters in s if a valid answer exists.
• Output:
• The shortest substring of s that contains exactly n distinct characters, or an indication that no such substring exists.

Examples

• Example 1:

• s = "aabcbc", n = 2

• Valid substrings with exactly 2 distinct characters include: "aa", "ab", "bc", "cb", etc.

• The shortest length is 2; any of "aa", "ab", "bc", "cb" is acceptable.

• Example 2:

• s = "abac", n = 3

• Substrings with exactly 3 distinct characters: "aba" (a, b), "abac" (a, b, c), "bac" (b, a, c)

• The shortest is "bac" of length 3.

• Example 3:

• s = "aaaa", n = 2

• There is no substring with exactly 2 distinct characters; return empty string or -1.

Task

1. Specify the algorithm to solve this problem, including:

• Time and space complexity.
• How you handle edge cases such as n = 0, n = 1, n > distinct characters in s, and very long strings.

1. Then implement the algorithm in a programming language of your choice.