Shortest Substring with Exactly K Unique Characters and Minimum Frequency Threshold
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.
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:
k unique characters.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 "".
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.
s will only contain lowercase English letters ('a' through 'z').k >= 1 and m >= 1.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
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).
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.
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.
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
1 <= s.length <= 10^51 <= k <= 26 (since s consists of lowercase English letters)1 <= m <= s.lengths consists only of lowercase English letters ('a'-'z').s.Loading editor...