mediumStringsPattern: Hash Maps
Shortest Substring of Dominant Characters Solution
Problem Statement
You are given a string s. A character is considered 'dominant' if its frequency of occurrence in s is equal to the maximum frequency of any character in s. Your task is to find the minimum length of a contiguous substring that contains all occurrences of at least one dominant character.
Examples
Example 1:
Input:s = "abcca"
Output:2
Explanation: The frequencies of characters are: 'a': 2, 'b': 1, 'c': 2. The maximum frequency is 2, so the dominant characters are 'a' and 'c'. All occurrences of 'a' are in the substring "abcca" (length 5). All occurrences of 'c' are in the substring "cc" (length 2). The minimum of these lengths is 2.
Example 2:
Input:s = "abcde"
Output:1
Explanation: All characters have a frequency of 1, so all characters ('a', 'b', 'c', 'd', 'e') are dominant. The shortest substring containing all occurrences of any of these is of length 1 (e.g., "a", "b", etc.).
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Time: O(N) Space: O(1)
Track the frequency, first occurrence index, and last occurrence index of each character during a single pass. Identify the maximum frequency, then check all characters with this frequency to find the minimum span between their first and last indices.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.