Maximum Number of Occurrences of a Substring
Asked at LinkedIn
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.