How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Find shortest substring with n unique letters

Quick Overview

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.

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

### 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`.

Quick Answer: 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.

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

Examples

Input: ("aabcbcdbca", 3)

Expected Output: 3

Explanation: The substring "bca" (and others like "cbd"/"dbc") has exactly 3 distinct characters with length 3, which is the shortest possible.

Input: ("aaaa", 1)

Expected Output: 1

Explanation: A single 'a' is a substring with exactly 1 distinct character, length 1.

Hints

A sliding window over s lets you track the count of distinct characters as you move the right edge.
Whenever the window contains more than n distinct characters, advance the left edge and decrement counts until you are back to at most n.
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.
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.