Maximum Number of Occurrences of a Substring - Video Solutions

Problem Overview: Given a string s, count how many times a substring appears while respecting two constraints: the substring length must be between minSize and maxSize, and it can contain at most maxLetters distinct characters. The goal is to return the maximum frequency of any valid substring.

Approach 1: Sliding Window Enumeration (O(n * (maxSize - minSize)), Space: O(n))

Use a sliding window to generate substrings between minSize and maxSize. For each window size, iterate across the string and track the number of unique characters using a frequency map. If the window satisfies the maxLetters constraint, record the substring in a hash table and increment its count. Continue scanning the string and keep track of the maximum frequency encountered.

This approach is straightforward because it directly follows the constraints in the problem statement. However, checking multiple window sizes increases the number of substrings processed. When maxSize - minSize is large, the total work grows quickly because each valid window requires substring extraction and hash map updates.

Approach 2: Hash Map Optimization with Fixed Window (O(n) time, O(n) space)

The key observation: the most frequent substring will always have length minSize. Longer substrings occur less frequently because they require more characters to match exactly. Once a substring of length minSize violates the maxLetters constraint, extending it only makes the condition harder to satisfy.

Use a fixed-size sliding window of length minSize. Maintain character counts inside the window and track the number of distinct characters. If the distinct count is ≤ maxLetters, extract the substring and update its count in a hash map. Slide the window by one character each step, updating the frequency map in constant time. Track the maximum occurrence as you go.

This reduces the search space dramatically. Instead of evaluating every possible substring length, you only evaluate windows of size minSize. Each character enters and leaves the window once, producing a linear scan over the string. Hash lookups remain constant time on average, making the entire algorithm O(n).

Recommended for interviews: The optimized sliding window with a hash map is the expected solution. It demonstrates pattern recognition and the ability to reduce unnecessary work using constraints. Explaining the naive enumeration approach first shows that you understand the problem space, but identifying that only minSize matters is the insight interviewers look for.