# 1297. Maximum Number of Occurrences of a Substring

## Description

Given a string s, return the maximum number of occurrences 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 occurrences 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.

## Solutions

• class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int ans = 0;
Map<String, Integer> cnt = new HashMap<>();
for (int i = 0; i < s.length() - minSize + 1; ++i) {
String t = s.substring(i, i + minSize);
Set<Character> ss = new HashSet<>();
for (int j = 0; j < minSize; ++j) {
}
if (ss.size() <= maxLetters) {
cnt.put(t, cnt.getOrDefault(t, 0) + 1);
ans = Math.max(ans, cnt.get(t));
}
}
return ans;
}
}

• class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int ans = 0;
unordered_map<string, int> cnt;
for (int i = 0; i < s.size() - minSize + 1; ++i) {
string t = s.substr(i, minSize);
unordered_set<char> ss(t.begin(), t.end());
if (ss.size() <= maxLetters) {
ans = max(ans, ++cnt[t]);
}
}
return ans;
}
};

• class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
ans = 0
cnt = Counter()
for i in range(len(s) - minSize + 1):
t = s[i : i + minSize]
ss = set(t)
if len(ss) <= maxLetters:
cnt[t] += 1
ans = max(ans, cnt[t])
return ans


• func maxFreq(s string, maxLetters int, minSize int, maxSize int) (ans int) {
cnt := map[string]int{}
for i := 0; i < len(s)-minSize+1; i++ {
t := s[i : i+minSize]
ss := map[rune]bool{}
for _, c := range t {
ss[c] = true
}
if len(ss) <= maxLetters {
cnt[t]++
if ans < cnt[t] {
ans = cnt[t]
}
}
}
return
}