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.
2. Then implement the algorithm in a programming language of your choice.