Maximum Number of Occurrences of a Substring - Solution & Explanation
Problem Statement
Given a string s, return the maximum number of occurrences of any substring under the following rules:
- The number of unique characters in the substring must be less than or equal to
maxLetters. - The substring size must be between
minSizeandmaxSizeinclusive.
Example 1:
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4 Output: 2 Explanation: Substring "aab" has 2 occurrences in the original string. It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
Example 2:
Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3 Output: 2 Explanation: Substring "aaa" occur 2 times in the string. It can overlap.
Constraints:
1 <= s.length <= 1051 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)sconsists of only lowercase English letters.
Approach Overview
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.
Approach 1: Sliding Window Approach
The sliding window technique is an efficient way to explore the substrings of size minSize. By fixing the size of the sliding window to minSize, we can evaluate each substring within the original string s. For each substring, we check if it contains the required number of unique characters. We use a frequency map to store each substring and its count of appearances.
This solution uses a sliding window approach where for each position we extract a substring of length minSize. We check if the substring meets the max character rule and if so, increment its counter. Finally, we fetch the maximum count from our counter.
Complexity
Time Complexity: O(n * minSize)
Space Complexity: O(n)
Approach 2: Hash Map Optimization
Instead of evaluating each substring separately, hash map optimization involves creating a frequency map directly based on extracted substrings. This way, one can efficiently record and retrieve the frequency of each substring.
This optimized approach uses a Counter to track frequency and defaultdict for current window unique character count. It slides across the string while only adjusting the counts of characters going out and coming into the window.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Hash Table + Enumeration
According to the problem description, if a long string meets the condition, then its substring of length minSize must also meet the condition. Therefore, we only need to enumerate all substrings of length minSize in s, then use a hash table to record the occurrence frequency of all substrings, and find the maximum frequency as the answer.
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n and m are the lengths of the string s and minSize, respectively. In this problem, m does not exceed 26.
Approach 4: Sliding Window + String Hashing
We can use a sliding window to maintain the number of distinct letters in the current substring, while using string hashing to efficiently calculate the hash value of substrings, thereby avoiding using strings as hash table keys and improving performance.
Specifically, we define a Hashing class to preprocess the prefix hash values and power values of the string s, so that we can calculate the hash value of any substring in O(1) time.
Then, we use a sliding window to traverse the string s, maintaining the number of distinct letters in the current window. When the window size reaches minSize, we calculate the hash value of the current substring and update its occurrence count. Next, we slide the window one position to the right and update the letter frequencies and the count of distinct letters.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n * minSize) |
| Hash Map Optimization | Time Complexity: O(n) |
| Hash Table + Enumeration | — |
| Sliding Window + String Hashing | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Enumeration | O(n * (maxSize - minSize)) | O(n) | When exploring all valid substring lengths or demonstrating the brute-force logic |
| Hash Map + Fixed Sliding Window | O(n) | O(n) | Best general solution; uses the insight that only minSize substrings matter |
Video Solution
Maximum Number of Occurrences of a Substring | LeetCode 1297 | Coders Camp • Coders Camp • 6,657 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Maximum Number of Occurrences of a Substring easy or hard?
Maximum Number of Occurrences of a Substring Python/Java solution
How to solve Maximum Number of Occurrences of a Substring in O(n)?
What is the best approach for Maximum Number of Occurrences of a Substring?
Is Maximum Number of Occurrences of a Substring asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Occurrences of a Substring?
What is the time complexity of Maximum Number of Occurrences of a Substring?
Ready to solve this problem?
Practice Maximum Number of Occurrences of a Substring with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor