Shortest Substring of Dominant Characters — Problem Statement & Solution Guide

StringsMediumHash Maps

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Shortest Substring of Dominant Characters problem optimally.

TopicStrings

PatternHash Maps

TimeO(n)

SpaceO(1)

Problem Description

You are provided with a string s composed exclusively of lowercase English letters. A character is classified as 'dominant' if its total occurrence count in s matches the highest frequency observed among all distinct characters in the string. For each dominant character c, define Occ(c) as the set of indices where c appears in s. A contiguous substring s[i..j] is considered to fully cover c if it includes every index belonging to Occ(c). Your task is to determine the minimum length of a contiguous substring that fully covers at least one dominant character. If no dominant character exists (which is impossible given the definition, but theoretically if the string is empty), return 0. However, since the string is non-empty, there is always at least one dominant character.

DSA Pattern Breakdown

"Shortest Substring of Dominant Characters"

medium

WHY DOES IT MATTER?

Identifying dominant characters and their minimal covering windows is a classic example of frequency analysis combined with range minimization, a pattern that appears in log analysis, DNA sequencing, and cache eviction policies where you need the smallest segment that satisfies a global constraint.

OPTIMIZATION CHALLENGE

The key insight is that you don't need to examine every possible substring. By recording only the first and last index for each character during the initial pass, you collapse the problem to a constant‑time lookup per dominant character, turning an O(n^2) search into O(n).

REAL-WORLD CONNECTION

Think of a distributed log where certain error codes dominate; you want the shortest time interval that captures every occurrence of the most frequent error to investigate its root cause. The algorithm mirrors scanning the log once to locate the first and last timestamps of each error type.

During an interview, quickly compute frequencies while iterating, and simultaneously update first/last positions. After the pass, filter characters with max frequency and compute spans; this one‑pass mindset often impresses interviewers.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to identifying the characters that appear most frequently (the dominant characters) and then finding the smallest window that contains every occurrence of each such character. A naive solution would scan the string for each character, count frequencies, and then for each dominant character recompute its first and last positions, leading to O(n^2) time in the worst case. The optimal paradigm leverages a single linear pass to gather frequency counts and simultaneously track the earliest and latest index for every character. Once the maximum frequency is known, the answer is simply the minimum span (last‑first+1) among the dominant characters. This approach exemplifies the "single‑pass frequency + sliding‑window" pattern, turning a potentially quadratic problem into O(n) time with O(1) extra space because the alphabet size (26 lowercase letters) is constant.

Interview Questions on This Problem

Q1How would you modify the solution if the string could contain any Unicode character, not just lowercase English letters?

Replace the fixed-size 26‑element arrays with hash maps to store frequency, first index, and last index for each distinct character. The algorithmic steps remain identical, still O(n) time, but space becomes O(k) where k is the number of unique characters in the input.

Q2Can you extend the problem to find the shortest substring that covers *all* characters whose frequency is at least a given threshold t?

First compute frequencies in one pass, collect characters with count ≥ t, then use a sliding window with a counter of how many of those required characters have been fully covered (i.e., the window contains all their occurrences). Expand and contract the window to maintain minimal length, yielding O(n) time.

Q3Why does the answer depend only on the first and last occurrence of a dominant character, and not on any interior positions?

By definition a substring fully covering a character must include every occurrence of that character. The minimal such substring is therefore bounded by the earliest and latest indices of that character; any interior occurrence is already inside this span, so the length cannot be reduced further.

Examples

Example 1

Input

s = "abac"

Output

Explanation: Frequencies: a=2, b=1, c=1. Max frequency is 2. Dominant character is 'a'. Occ('a') = {0, 2}. The shortest substring covering indices 0 and 2 is s[0..2] = "aba", which has length 3.

Example 2

Input

s = "xyzxyz"

Output

Explanation: Frequencies: x=2, y=2, z=2. Max frequency is 2. All characters x, y, z are dominant. Occ('x') = {0, 3}, Occ('y') = {1, 4}, Occ('z') = {2, 5}. Shortest substring for 'x' is s[0..3] (length 4), for 'y' is s[1..4] (length 4), for 'z' is s[2..5] (length 4). The minimum length is 4. Wait, let me re-evaluate. s[0..3] is "xyxz" length 4. s[1..4] is "yzxy" length 4. s[2..5] is "zxyz" length 4. The minimum is 4. Let me correct the output to 4.

Example 3

Input

s = "aabbcc"

Output

Explanation: Frequencies: a=2, b=2, c=2. Max frequency is 2. All characters are dominant. Occ('a') = {0, 1}, Occ('b') = {2, 3}, Occ('c') = {4, 5}. Shortest substring for 'a' is s[0..1] (length 2), for 'b' is s[2..3] (length 2), for 'c' is s[4..5] (length 2). The minimum length is 2.

Example 4

Input

s = "abcabcabc"

Output

Explanation: Frequencies: a=3, b=3, c=3. Max frequency is 3. All characters are dominant. Occ('a') = {0, 3, 6}, Occ('b') = {1, 4, 7}, Occ('c') = {2, 5, 8}. Shortest substring for 'a' is s[0..6] (length 7), for 'b' is s[1..7] (length 7), for 'c' is s[2..8] (length 7). The minimum length is 7.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters only

Optimal Approach & Strategy

Perform a single pass to gather frequencies and first/last positions, then compute the minimal span for each dominant character in O(1) per character, yielding overall O(n) time.

Brute Force Approach

Iterate over every possible substring, for each check if it contains all occurrences of a dominant character, and keep the minimum length; this is O(n^3) in the worst case.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

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_len

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;
}

Asked in Top Tech Interviews

Cred

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.