Shortest Substring of Dominant Characters — Problem Statement & Solution Guide
Problem Description
Given a string s, find the minimum length of a contiguous substring that contains all occurrences of at least one dominant character. A character is considered 'dominant' if its frequency of occurrence in s is equal to the maximum frequency of any character in s.
Examples
Input
abba
Output
ab
Explanation: Step-by-step: The dominant character 'a' occurs twice, which is the maximum frequency. The substring 'ab' contains all occurrences of 'a' and it's the shortest possible substring.
Input
abcde
Output
a
Explanation: Step-by-step: The dominant character 'a' occurs twice, which is the maximum frequency. The substring 'a' contains all occurrences of 'a' and it's the shortest possible substring.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Optimal Approach & Strategy
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.
Brute Force Approach
Generate all possible contiguous substrings, check which ones contain all occurrences of at least one dominant character, and find the minimum length among them. This requires O(N^2) or O(N^3) time complexity.
Verified Code Solutions
function solution(s) {
const maxFrequency = {};
let maxCount = 0;
for (let char of s) {
maxFrequency[char] = (maxFrequency[char] || 0) + 1;
maxCount = Math.max(maxCount, maxFrequency[char]);
}
const dominantChars = Object.keys(maxFrequency).filter(char => maxFrequency[char] === maxCount);
let minLen = Infinity;
for (let char of dominantChars) {
let start = 0;
let end = 0;
let count = 0;
while (end < s.length) {
if (s[end] === char) {
count++;
}
if (count === maxCount) {
while (start <= end && count === maxCount) {
if (s[start] === char) {
count--;
}
start++;
}
minLen = Math.min(minLen, end - start + 1);
}
end++;
}
}
return minLen === Infinity ? -1 : minLen;
}class Solution {
public:
int solution(string s) {
map<char, int> maxFrequency;
int maxCount = 0;
for (char c : s) {
maxFrequency[c]++;
maxCount = max(maxCount, maxFrequency[c]);
}
vector<char> dominantChars;
for (auto it = maxFrequency.begin(); it != maxFrequency.end(); ++it) {
if (it->second == maxCount) {
dominantChars.push_back(it->first);
}
}
int minLen = INT_MAX;
for (char c : dominantChars) {
int start = 0;
int end = 0;
int count = 0;
while (end < s.length()) {
if (s[end] == c) {
count++;
}
if (count == maxCount) {
while (start <= end && count == maxCount) {
if (s[start] == c) {
count--;
}
start++;
}
minLen = min(minLen, end - start + 1);
}
end++;
}
}
return minLen == INT_MAX ? -1 : minLen;
}
};class Solution {
public int solution(String s) {
Map<Character, Integer> maxFrequency = new HashMap<>();
int maxCount = 0;
for (char c : s.toCharArray()) {
maxFrequency.put(c, maxFrequency.getOrDefault(c, 0) + 1);
maxCount = Math.max(maxCount, maxFrequency.get(c));
}
List<Character> dominantChars = new ArrayList<>();
for (char c : maxFrequency.keySet()) {
if (maxFrequency.get(c) == maxCount) {
dominantChars.add(c);
}
}
int minLen = Integer.MAX_VALUE;
for (char c : dominantChars) {
int start = 0;
int end = 0;
int count = 0;
while (end < s.length()) {
if (s.charAt(end) == c) {
count++;
}
if (count == maxCount) {
while (start <= end && count == maxCount) {
if (s.charAt(start) == c) {
count--;
}
start++;
}
minLen = Math.min(minLen, end - start + 1);
}
end++;
}
}
return minLen == Integer.MAX_VALUE ? -1 : minLen;
}
}def solution(s):
max_frequency = {}
max_count = 0
for char in s:
max_frequency[char] = (max_frequency.get(char, 0) + 1)
max_count = max(max_count, max_frequency[char])
dominant_chars = [char for char in max_frequency if max_frequency[char] == max_count]
min_len = float('inf')
for char in dominant_chars:
start = 0
end = 0
count = 0
while end < len(s):
if s[end] == char:
count += 1
if count == max_count:
while start <= end and count == max_count:
if s[start] == char:
count -= 1
start += 1
min_len = min(min_len, end - start + 1)
end += 1
if min_len == float('inf'):
return -1
return min_lenfunction solution(s) {
const maxFrequency = {};
let maxCount = 0;
for (let char of s) {
maxFrequency[char] = (maxFrequency[char] || 0) + 1;
maxCount = Math.max(maxCount, maxFrequency[char]);
}
const dominantChars = Object.keys(maxFrequency).filter(char => maxFrequency[char] === maxCount);
let minLen = Infinity;
for (let char of dominantChars) {
let start = 0;
let end = 0;
let count = 0;
while (end < s.length) {
if (s[end] === char) {
count++;
}
if (count === maxCount) {
while (start <= end && count === maxCount) {
if (s[start] === char) {
count--;
}
start++;
}
minLen = Math.min(minLen, end - start + 1);
}
end++;
}
}
return minLen === Infinity ? -1 : minLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.