Katkat
Back

Find shortest substring with n unique letters

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.