Maximum Number of Occurrences of a Substring
Maximum Number of Occurrences of a Substring is a medium arrays & hashing problem solved with the sliding window · hash map pattern.
The best approach, optimal (fixed window of minsize), runs in O(n · minSize) time and O(n · minSize) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every length, every start) up.
Problem
You are given a string s of lowercase letters and three integers maxLetters, minSize and maxSize. A substring is allowed if it contains at most maxLetters distinct letters and its length is between minSize and maxSize inclusive.
Return the largest number of times any single allowed substring occurs in s. Occurrences may overlap. If no substring is allowed, return 0.
Examples
Example 1
- Input
s = "abcabcab", maxLetters = 3, minSize = 2, maxSize = 3- Output
3- Why
- "ab" starts at positions 0, 3 and 6 and uses only 2 distinct letters. No allowed substring appears more often.
Example 2
- Input
s = "zzzz", maxLetters = 1, minSize = 2, maxSize = 3- Output
3- Why
- "zz" starts at positions 0, 1 and 2; occurrences may overlap.
Example 3
- Input
s = "abcd", maxLetters = 2, minSize = 3, maxSize = 4- Output
0- Why
- Every substring of length 3 or 4 has at least 3 distinct letters, so none is allowed.
Constraints
1 <= s.length <= 10^51 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)scontains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every length, every start) | O(n · L²) | O(n · L²) |
| Optimal (fixed window of minSize) | O(n · minSize) | O(n · minSize) |
1Brute force (every length, every start)
O(n · L²)There are n starts for each of up to L = maxSize - minSize + 1 lengths, and each substring costs O(L) to build and scan (L <= 26).O(n · L²)The hash map can store a substring of up to 26 letters for every start and length.For every length from minSize to maxSize and every start position, take the substring, count its distinct letters, and if it is within the limit add one to its count in a hash map. The answer is the largest count.
- For len = minSize..maxSize and i = 0..n - len: sub = s[i, i + len).
- Count distinct letters of sub; if <= maxLetters, increment freq[sub].
- Return the maximum value in freq, or 0 if it is empty.
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> freq = new HashMap<>();
int best = 0, n = s.length();
for (int len = minSize; len <= maxSize; len++) {
for (int i = 0; i + len <= n; i++) {
String sub = s.substring(i, i + len);
boolean[] seen = new boolean[26];
int distinct = 0;
for (int j = 0; j < len; j++) {
int c = sub.charAt(j) - 'a';
if (!seen[c]) { seen[c] = true; distinct++; }
}
if (distinct <= maxLetters) {
int f = freq.merge(sub, 1, Integer::sum);
best = Math.max(best, f);
}
}
}
return best;
}
}class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
freq = {}
best = 0
n = len(s)
for length in range(minSize, maxSize + 1):
for i in range(n - length + 1):
sub = s[i:i + length]
if len(set(sub)) <= maxLetters:
freq[sub] = freq.get(sub, 0) + 1
best = max(best, freq[sub])
return bestclass Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map<string, int> freq;
int best = 0, n = s.size();
for (int len = minSize; len <= maxSize; len++) {
for (int i = 0; i + len <= n; i++) {
string sub = s.substr(i, len);
bool seen[26] = {false};
int distinct = 0;
for (char ch : sub) {
if (!seen[ch - 'a']) { seen[ch - 'a'] = true; distinct++; }
}
if (distinct <= maxLetters) best = max(best, ++freq[sub]);
}
}
return best;
}
};function maxFreq(s, maxLetters, minSize, maxSize) {
const freq = new Map();
let best = 0;
const n = s.length;
for (let len = minSize; len <= maxSize; len++) {
for (let i = 0; i + len <= n; i++) {
const sub = s.substring(i, i + len);
if (new Set(sub).size <= maxLetters) {
const f = (freq.get(sub) || 0) + 1;
freq.set(sub, f);
best = Math.max(best, f);
}
}
}
return best;
}2Optimal (fixed window of minSize)
O(n · minSize)The window moves in O(1) per step, and hashing each window's text costs O(minSize) with minSize <= 26.O(n · minSize)The map may hold up to n different windows of minSize letters.A valid longer substring always contains a valid substring of length minSize (its prefix has no more distinct letters) that occurs at least as often, so maxSize can be ignored. Slide one window of length minSize, keeping a count per letter and the number of distinct letters. Whenever the window has at most maxLetters distinct letters, add the window's text to a frequency map.
- Keep cnt[26] and distinct; for right = 0..n - 1 add s[right] (distinct++ when its count goes 0 -> 1).
- If the window is longer than minSize, remove s[right - minSize] (distinct-- when its count goes 1 -> 0).
- When the window has exactly minSize letters and distinct <= maxLetters, increment freq of that substring and update the best.
- Return the best count.
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> freq = new HashMap<>();
int[] cnt = new int[26];
int distinct = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
if (cnt[s.charAt(right) - 'a']++ == 0) distinct++;
int left = right - minSize + 1;
if (left > 0 && --cnt[s.charAt(left - 1) - 'a'] == 0) distinct--;
if (left >= 0 && distinct <= maxLetters) {
int f = freq.merge(s.substring(left, right + 1), 1, Integer::sum);
best = Math.max(best, f);
}
}
return best;
}
}class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
freq = {}
cnt = [0] * 26
distinct = best = 0
for right, ch in enumerate(s):
c = ord(ch) - 97
if cnt[c] == 0:
distinct += 1
cnt[c] += 1
left = right - minSize + 1
if left > 0:
d = ord(s[left - 1]) - 97
cnt[d] -= 1
if cnt[d] == 0:
distinct -= 1
if left >= 0 and distinct <= maxLetters:
sub = s[left:right + 1]
freq[sub] = freq.get(sub, 0) + 1
best = max(best, freq[sub])
return bestclass Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map<string, int> freq;
int cnt[26] = {0};
int distinct = 0, best = 0, n = s.size();
for (int right = 0; right < n; right++) {
if (cnt[s[right] - 'a']++ == 0) distinct++;
int left = right - minSize + 1;
if (left > 0 && --cnt[s[left - 1] - 'a'] == 0) distinct--;
if (left >= 0 && distinct <= maxLetters) {
best = max(best, ++freq[s.substr(left, minSize)]);
}
}
return best;
}
};function maxFreq(s, maxLetters, minSize, maxSize) {
const freq = new Map();
const cnt = new Array(26).fill(0);
let distinct = 0, best = 0;
for (let right = 0; right < s.length; right++) {
if (cnt[s.charCodeAt(right) - 97]++ === 0) distinct++;
const left = right - minSize + 1;
if (left > 0 && --cnt[s.charCodeAt(left - 1) - 97] === 0) distinct--;
if (left >= 0 && distinct <= maxLetters) {
const sub = s.substring(left, right + 1);
const f = (freq.get(sub) || 0) + 1;
freq.set(sub, f);
best = Math.max(best, f);
}
}
return best;
}Edge cases to test
- No substring satisfies the letter limit (answer 0)
- A string of one repeated letter, where occurrences overlap
minSize == maxSizeminSize = 1: the answer is the count of the most frequent lettermaxSizelarger than needed: longer windows never beat shorter ones
Hints
Hint 1
Try every allowed length and every start position, count distinct letters, and tally the valid substrings in a hash map.
Hint 2
If a substring of length L > minSize is valid and appears c times, its first minSize letters form a valid substring that appears at least c times.
Hint 3
So only length minSize matters. Slide a window of that length across s, keep letter counts to know the number of distinct letters, and count the windows that qualify.
FAQ
What is the best time complexity for Maximum Number of Occurrences of a Substring?
Optimal (fixed window of minSize) runs in O(n · minSize) time and O(n · minSize) extra space. The window moves in O(1) per step, and hashing each window's text costs O(minSize) with minSize <= 26.
Which pattern does Maximum Number of Occurrences of a Substring use?
It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters, Minimum Window Substring, Longest Substring with At Most K Distinct Characters.
Is there a brute force solution for Maximum Number of Occurrences of a Substring?
Yes. Brute force (every length, every start) takes O(n · L²) time and O(n · L²) space. For every length from minSize to maxSize and every start position, take the substring, count its distinct letters, and if it is within the limit add one to its count in a hash map.
Which edge cases should I test for Maximum Number of Occurrences of a Substring?
No substring satisfies the letter limit (answer 0); A string of one repeated letter, where occurrences overlap; minSize == maxSize; minSize = 1: the answer is the count of the most frequent letter; maxSize larger than needed: longer windows never beat shorter ones.