1297. Maximum Number of Occurrences of a Substring
Asked at LinkedIn
Difficulty
Medium
Time
O(n * minSize)
Space
O(n * minSize)
Pattern
Hash Table
Companies
1
Problem
You are given a string s and three integers: maxLetters, minSize, and maxSize. Consider every substring of s (a run of characters that sit next to each other). A substring is valid if it has at most maxLetters distinct characters, and its length is between minSize and maxSize inclusive.
Return the largest number of times any valid substring appears in s. Occurrences may overlap — for example, "aaa" appears twice in "aaaa" (positions 0-2 and 1-3).
The key observation is that maxSize never matters. If a longer substring appears c times, then its first minSize characters also appear at least c times, and a shorter prefix cannot have more distinct letters. So the best answer is always reached by some substring of length exactly minSize.
Only length-minSize windows matter
Constraints
- ●
1 <= s.length <= 10^5 - ●
1 <= maxLetters <= 26 - ●
1 <= minSize <= maxSize <= min(26, s.length) - ●
s consists of only lowercase English letters
Examples
s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 42s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 32Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Medium | View all LinkedIn questions → |
How to Think About It
Checking every length from minSize to maxSize multiplies the work.
Key insight: if a longer substring occurs c times, its first minSize characters also occur at least c times — and they satisfy the distinct-letter limit, since a prefix has no more distinct letters. So the best answer is always achieved by some length-minSize substring.
Slide a window of exactly minSize characters. Maintain letter counts to know the number of distinct letters in the window.
For each window with at most maxLetters distinct letters, increment its count in a hash map. The answer is the largest count.
Walkthrough for "aababcaab", maxLetters = 2, minSize = 3: windows aab (valid), aba, bab, abc (3 distinct, skip), bca (skip), caa, aab -> aab appears twice. Answer 2.
Optimal Approach
Step 1: freq = {}, letter counts cnt, distinct = 0.
Step 2: For i in range n:
Add s[i] to cnt (update distinct).
If i >= minSize, remove s[i - minSize] (update distinct).
If i >= minSize - 1 and distinct <= maxLetters: freq[s[i-minSize+1 .. i]] += 1.
Step 3: Return max(freq.values()) or 0.
Time: O(n * minSize) for slicing (O(n) with rolling hash). Space: O(n * minSize).
Sliding window with a frequency map
What Trips People Up in Real Interviews
Iterating over every length up to maxSize. Explain why minSize alone suffices — that argument is the core of the problem.
Recounting distinct letters from scratch for every window. Maintain counts incrementally.
Counting overlapping occurrences incorrectly — overlapping occurrences do count here, and the sliding window counts them naturally.
Returning the substring instead of its count.
Solution Code
O(n * minSize) timedef maxFreq(s, maxLetters, minSize, maxSize):
freq = {}
cnt = {}
distinct = 0
for i, ch in enumerate(s):
cnt[ch] = cnt.get(ch, 0) + 1
if cnt[ch] == 1:
distinct += 1
if i >= minSize:
old = s[i - minSize]
cnt[old] -= 1
if cnt[old] == 0:
distinct -= 1
if i >= minSize - 1 and distinct <= maxLetters:
sub = s[i - minSize + 1:i + 1]
freq[sub] = freq.get(sub, 0) + 1
return max(freq.values(), default=0)Frequently Asked Questions
What is the Maximum Number of Occurrences of a Substring problem?
Maximum Number of Occurrences of a Substring asks for the highest count of any substring whose length is between `minSize` and `maxSize` and that has at most `maxLetters` distinct characters. The trick is realizing that `maxSize` is a red herring — only substrings of length `minSize` matter.
How do you solve Maximum Number of Occurrences of a Substring?
The optimal approach runs in O(n * minSize) time and O(n * minSize) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Maximum Number of Occurrences of a Substring?
Maximum Number of Occurrences of a Substring is asked at LinkedIn. It is a medium difficulty problem.
What are common mistakes on Maximum Number of Occurrences of a Substring?
- Iterating over every length up to `maxSize`. Explain why `minSize` alone suffices — that argument is the core of the problem.
- Recounting distinct letters from scratch for every window. Maintain counts incrementally.
- Counting overlapping occurrences incorrectly — overlapping occurrences do count here, and the sliding window counts them naturally.
- Returning the substring instead of its count.