# 1297. Maximum Number of Occurrences of a Substring

Given a string `s`, return the maximum number of ocurrences of any substring under the following rules:

• The number of unique characters in the substring must be less than or equal to `maxLetters`.
• The substring size must be between `minSize` and `maxSize` inclusive.

Example 1:

``````Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
``````

Example 2:

``````Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.
``````

Constraints:

• `1 <= s.length <= 105`
• `1 <= maxLetters <= 26`
• `1 <= minSize <= maxSize <= min(26, s.length)`
• `s` consists of only lowercase English letters.

``````class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int res = 0, n = s.size();
unordered_map<string, int> strCnt;
for (int i = 0; i <= n - minSize; ++i) {
string cur = s.substr(i, minSize);
if (isValid(cur, maxLetters)) {
res = max(res, ++strCnt[cur]);
}
}
return res;
}
bool isValid(string cur, int maxLetters) {
unordered_set<char> st;
for (char c : cur) st.insert(c);
return st.size() <= maxLetters;
}
};
``````

``````class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int res = 0, start = 0, n = s.size();
unordered_map<char, int> charCnt;
unordered_map<string, int> strCnt;
for (int i = 0; i < n; ++i) {
++charCnt[s[i]];
if (i - start + 1 > minSize) {
if (--charCnt[s[start]] == 0) charCnt.erase(s[start]);
++start;
}
if (i - start + 1 == minSize && charCnt.size() <= maxLetters) {
res = max(res, ++strCnt[s.substr(start, i - start + 1)]);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1297

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/888643/Java-easy-to-understand-solution-O(n)

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457577/C%2B%2B-Greedy-approach-%2B-Sliding-window-O(n).

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation