Frontend School

Shortest Substring with Exactly K Unique Characters and Minimum Frequency Threshold

DSA
hard

Shortest Substring with Exactly K Unique Characters and Minimum Frequency Threshold

Hard
String
Sliding Window
Hash Map

Overview

In real-world data processing, such as analyzing user input patterns or parsing communication logs, it's often critical to identify sequences that exhibit specific structural properties. This problem challenges you to find the most concise segment of a string that meets precise criteria regarding its character diversity and repetition. Efficiently solving this is crucial for optimizing data filtering and pattern recognition systems at scale.

What you need to do / Task

Your task is to implement a function findShortestSubstring that takes a string s, an integer k, and an integer m. The function should identify and return the shortest substring of s that satisfies all the following conditions:

  1. The substring must contain exactly k unique characters.
  2. Each of these k unique characters must appear at least m times within the substring.

If there are multiple substrings of the same minimum length that satisfy the conditions, any one of them is an acceptable answer. If no such substring exists, the function should return an empty string "".

Input & output

  • s: A string consisting of lowercase English letters.
  • k: An integer representing the exact number of unique characters required in the substring.
  • m: An integer representing the minimum frequency each of the k unique characters must have within the substring.

Returns: The shortest substring of s that meets the criteria, or "" if no such substring exists.

Clarifications

  • s will only contain lowercase English letters ('a' through 'z').
  • The problem implies k >= 1 and m >= 1.
  • If k is greater than the total number of unique characters available in s, or m is too high for any character to reach that frequency, a valid substring might not exist.

Examples

1

Example 1

Input:

s = "aaabbbccc", k = 2, m = 2

Output:

"aabb"

Note:

The substring "aabb" contains exactly 2 unique characters ('a' and 'b'). 'a' appears 2 times (>=2) and 'b' appears 2 times (>=2). Its length is 4. "bbcc" is another valid substring of length 4. "aaabbb" is valid but longer (length 6).

2

Example 2

Input:

s = "abccbaac", k = 2, m = 2

Output:

"bccb"

Note:

The substring "bccb" contains exactly 2 unique characters ('b' and 'c'). 'b' appears 2 times (>=2) and 'c' appears 2 times (>=2). Its length is 4. "aacc" is another valid substring of length 4.

3

Example 3

Input:

s = "abcde", k = 3, m = 2

Output:

""

Note:

No substring in "abcde" can have 3 unique characters where each appears at least 2 times, as all characters appear only once.

4

Example 4

Input:

s = "topcoder", k = 1, m = 3

Output:

""

Note:

No character in "topcoder" appears 3 or more times. Thus, no substring can satisfy the condition for m=3.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= k <= 26 (since s consists of lowercase English letters)
  • 1 <= m <= s.length
  • s consists only of lowercase English letters ('a'-'z').

Out of scope

  • Handling non-alphabetic characters or Unicode characters.
  • Considering case-insensitivity; assume all inputs are lowercase.

What interviewers evaluate

  • Correctness: The solution must accurately identify the shortest valid substring for all valid inputs and edge cases.
  • Efficiency: The solution should demonstrate optimal time and space complexity, typically achieving O(N) time complexity where N is the length of s.
  • Code Quality: The code should be clean, readable, well-structured, and use appropriate data structures.
  • Problem-Solving: Ability to adapt the sliding window technique to handle multiple, complex conditions simultaneously.

Loading editor...