1297. Maximum Number of Occurrences of a Substring - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a string s and three integers maxLetters, minSize, and maxSize, find the maximum number of occurrences of any substring of s that meets the following conditions:

The substring’s length is between minSize and maxSize (inclusive).
The substring contains at most maxLetters unique characters.

Return the maximum number of occurrences among all such substrings. If no substring meets the conditions, return 0.

Examples:

Example 1:
- Input:
  s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
- Output: 2
- Explanation:
  The substring "aab" appears 2 times and contains 2 unique letters which is within the allowed limit. Although "aba" also appears, its frequency is lower.
Example 2:
- Input:
  s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
- Output: 2
- Explanation:
  The substring "aaa" appears 2 times and contains only 1 unique letter, satisfying the condition.
Example 3:
- Input:
  s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
- Output: 0
- Explanation:
  No substring of length 3 in "abcde" contains at most 2 distinct letters since all such substrings have 3 distinct letters.

Constraints:

The length of s is up to 10^5.
1 <= maxLetters, minSize, maxSize <= s.length
The string s consists of lowercase English letters.

Hints Before the Solution

Sliding Window Insight:
Consider using a sliding window to efficiently count substrings of fixed length (minSize). Notice that if a longer substring satisfies the condition, its shorter substring (of length minSize) is also valid and will have a higher occurrence frequency.
Unique Characters Count:
Use a frequency count (or set) to determine the number of unique letters in the current window. This will help you quickly check if the substring meets the maxLetters condition.

Approaches

Approach 1: Brute Force

Idea:

Generate every possible substring with lengths from minSize to maxSize.
For each substring, count the unique letters.
If the substring meets the condition (unique count ≤ maxLetters), record its frequency.
Finally, return the maximum frequency found.

Issues:

This approach involves nested loops and checking many substrings, which can be very slow (O(n²) or worse) for large strings.

When to use:

Only for very small inputs or for understanding the problem logic.

Approach 2: Optimal Sliding Window (Using Fixed Window of Length `minSize`)

Observation:

Although the allowed substring length can range up to maxSize, it turns out that the optimal candidate is always of length minSize.
Reason: If a longer substring satisfies the condition, its substring of length minSize will also satisfy the condition and will appear more frequently.

Steps:

Initialize a sliding window of size minSize.
For each window:
- Count the number of unique letters.
- If the unique count is ≤ maxLetters, add (or update) the frequency of that substring in a dictionary.
Return the highest frequency from the dictionary.

Advantages:

This approach only requires scanning the string once, making it O(n) in time.

Code Solutions

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time Complexity:
- The sliding window runs in O(n) where n is the length of the string.
- For each window, counting unique characters takes O(minSize) in the worst case.
- Overall, the complexity is O(n * minSize), which is acceptable given the constraints.
Space Complexity:
- The frequency dictionary (or map) may store up to O(n) substrings in the worst case.
- Thus, the space complexity is O(n).

Step-by-Step Walkthrough with Visual Example

Let’s consider the string s = "aababcaab" with maxLetters = 2, minSize = 3:

Window 1 (i = 0):
- Substring: "aab"
- Unique letters: {a, b} (2 unique letters, valid)
- Frequency count: {"aab": 1}
Window 2 (i = 1):
- Substring: "aba"
- Unique letters: {a, b} (2 unique letters, valid)
- Frequency count: {"aab": 1, "aba": 1}
Window 3 (i = 2):
- Substring: "bab"
- Unique letters: {a, b} (valid)
- Frequency count: {"aab": 1, "aba": 1, "bab": 1}
Window 4 (i = 3):
- Substring: "abc"
- Unique letters: {a, b, c} (3 unique letters, invalid)
- Frequency remains unchanged.
Continue sliding the window:
- Update counts accordingly. At the end, the substring "aab" is found twice, which is the maximum occurrence.

Common Mistakes

Overcomplicating with maxSize:
Many mistakenly try to consider all lengths from minSize to maxSize. However, note that focusing on minSize is enough because longer valid substrings will always have a shorter valid substring with higher or equal frequency.
Inefficient Unique Count Calculation:
Recalculating the unique count from scratch for every window can be optimized. Although in our explanation we simply convert the substring to a set, in a sliding window you could also update the count as you slide (advanced optimization).
Ignoring Edge Cases:
Not handling cases where no valid substring exists or where the string length is smaller than minSize.

Edge Cases

String length < minSize:
Return 0 immediately since no substring of the required length can be formed.
No valid substring found:
If no substring meets the unique letters condition, ensure the function returns 0.
All characters are the same:
The entire string might be valid and every window could be the same.

Alternative Variation:
What if you need to count substrings with exactly maxLetters distinct characters? This would require a slight modification in the check.
Related Problems for Further Practice:
- Longest Substring Without Repeating Characters
- Substring with Concatenation of All Words
- Longest Repeating Character Replacement
- Find All Anagrams in a String