How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

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

What role is this question designed for?

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

Find shortest substring with N unique characters

Q: Find shortest substring with N unique characters

This question evaluates proficiency in string processing, handling character-uniqueness constraints, and algorithmic thinking about time and space efficiency.

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

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

You are given a string s and an integer n.

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

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

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

Find shortest substring with N unique characters

Quick Overview

Requirements

Examples

Task

Submit Your Answer

Find shortest substring with N unique characters

Quick Overview

Requirements

Examples

Task

Submit Your Answer