cswork / libraryOpen practice workspace

Coding questions · Microsoft

Find shortest substring with n unique letters

This question evaluates proficiency in string processing, frequency management, and algorithmic optimization for locating constrained contiguous substrings. Commonly asked in the coding & algorithms domain because it reveals how candidates reason about character distinctness and efficiency trade-offs, it targets practical application of algorithmic techniques rather than purely conceptual theory.

Problem

You are given a string s consisting of lowercase English letters and an integer n (1 ≤ n ≤ 26).

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

If no such substring exists, return -1.

Example

  • Input: s = "aabcbcdbca", n = 3
  • One shortest substring with exactly 3 distinct characters is "bca" (length 3), so the output should be 3.

Find Shortest Substring with Exactly N Unique Letters

You are given a string s consisting of lowercase English letters and an integer n (1 ≤ n ≤ 26).

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

If no such substring exists, return -1.

Example

  • Input: s = "aabcbcdbca", n = 3
  • Output: 3 (e.g. the substring "bca" has exactly 3 distinct characters and length 3).

Approach hint: Use a sliding window. Expand the right edge; whenever the window holds more than n distinct characters, shrink from the left until it is at most n. Each time the window has exactly n distinct characters, greedily trim leading characters whose count is greater than 1 to get the tightest window ending at the current right index, and record its length.

Constraints

  • 1 ≤ n ≤ 26
  • 0 ≤ |s| ≤ 10^5
  • s consists only of lowercase English letters
  • Return -1 when no substring has exactly n distinct characters

Hints

  1. A sliding window over s lets you track the count of distinct characters as you move the right edge.
  2. Whenever the window contains more than n distinct characters, advance the left edge and decrement counts until you are back to at most n.
  3. When the window has exactly n distinct characters, you can still shrink it: drop leading characters whose count is greater than 1, since removing them does not reduce the distinct count.
  4. If you never reach a window with exactly n distinct characters (e.g. the string has fewer than n distinct letters), the answer is -1.