Maximum Number of Occurrences of a Substring — Solution
Maximum Number of Occurrences of a Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Occurrences of a Substring is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, return the maximum number of occurrences of any substring that satisfies both rules:
- it contains at most
maxLettersdistinct characters; - its length is between
minSizeandmaxSizeinclusive.
If no substring qualifies, return 0.
Example 1
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: "aab" occurs twice and has two distinct letters.
Example 2
Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: "aaa" occurs at indices 0 and 1.
Example 3
Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0
Constraints
1 <= s.length <= 1000001 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)
Hints for Maximum Number of Occurrences of a Substring
Hint 1
maxSizeis a red herring. Why would a longer substring ever beat a shorter one?Hint 2
Any occurrence of a longer valid substring contains an occurrence of its length-
minSizeprefix, which is also valid.Hint 3
So only windows of exactly
minSizeneed counting.
How to solve Maximum Number of Occurrences of a Substring
Only length minSize matters. A substring of length L > minSize that occurs k times has a prefix of length minSize occurring at least k times, with no more distinct letters — so the shortest allowed window always ties or wins.
Approach
- Slide a window of exactly
minSizecharacters acrosss. - For each window, count its distinct characters and skip it if that exceeds
maxLetters. - Tally the window's text in a hash map and keep the running maximum tally.
Why it works
Every occurrence of a longer valid substring yields an occurrence of its minSize prefix at the same start, so the prefix's count is at least as large; and a prefix has a subset of the letters, so it is still within maxLetters. The maximum over length-minSize windows is therefore the global maximum.
Complexity
- Time —
O(n · minSize) - Space —
O(n · minSize)
Pitfalls
- Enumerating every length from
minSizetomaxSizeis correct but does far more work than needed. - Forgetting the distinct-letter check counts substrings that violate
maxLetters.
Reference solution
Python
def maxFreq(s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
count = {}
best = 0
for i in range(len(s) - minSize + 1):
sub = s[i:i + minSize]
if len(set(sub)) > maxLetters:
continue
count[sub] = count.get(sub, 0) + 1
best = max(best, count[sub])
return bestJava
public static int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> count = new HashMap<>();
int best = 0;
for (int i = 0; i + minSize <= s.length(); i++) {
String sub = s.substring(i, i + minSize);
Set<Character> seen = new HashSet<>();
for (int j = 0; j < sub.length(); j++) seen.add(sub.charAt(j));
if (seen.size() > maxLetters) continue;
int c = count.getOrDefault(sub, 0) + 1;
count.put(sub, c);
if (c > best) best = c;
}
return best;
}C++
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map<string, int> count;
int best = 0;
for (int i = 0; i + minSize <= (int) s.size(); i++) {
string sub = s.substr(i, minSize);
vector<bool> seen(26, false);
int distinct = 0;
for (char c : sub) {
if (!seen[c - 'a']) { seen[c - 'a'] = true; distinct++; }
}
if (distinct > maxLetters) continue;
int c = ++count[sub];
if (c > best) best = c;
}
return best;
}JavaScript
var maxFreq = function(s, maxLetters, minSize, maxSize) {
var count = {}, best = 0;
for (var i = 0; i + minSize <= s.length; i++) {
var sub = s.substr(i, minSize);
var seen = {}, distinct = 0;
for (var j = 0; j < sub.length; j++) {
var c = sub.charAt(j);
if (seen[c] !== true) { seen[c] = true; distinct++; }
}
if (distinct > maxLetters) continue;
count[sub] = (count[sub] === undefined ? 0 : count[sub]) + 1;
if (count[sub] > best) best = count[sub];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets