# 1297. Maximum Number of Occurrences of a Substring¶

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { // Greedily consider strings with minSize, so ignore maxSize. int ans = 0; int letters = 0; vector count(26); unordered_map substringCount; for (int l = 0, r = 0; r < s.length(); ++r) { if (++count[s[r] - 'a'] == 1) ++letters; while (letters > maxLetters || r - l + 1 > minSize) if (--count[s[l++] - 'a'] == 0) --letters; if (r - l + 1 == minSize) ans = max(ans, ++substringCount[s.substr(l, minSize)]); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int maxFreq(String s, int maxLetters, int minSize, int maxSize) { // Greedily consider strings with minSize, so ignore maxSize. int ans = 0; int letters = 0; int[] count = new int[26]; Map substringCount = new HashMap<>(); for (int l = 0, r = 0; r < s.length(); ++r) { if (++count[s.charAt(r) - 'a'] == 1) ++letters; while (letters > maxLetters || r - l + 1 > minSize) if (--count[s.charAt(l++) - 'a'] == 0) --letters; if (r - l + 1 == minSize) ans = Math.max(ans, substringCount.merge(s.substring(l, l + minSize), 1, Integer::sum)); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: # Greedily consider strings with minSize, so ignore maxSize. ans = 0 letters = 0 count = collections.Counter() substringCount = collections.Counter() l = 0 for r, c in enumerate(s): count[c] += 1 if count[c] == 1: letters += 1 while letters > maxLetters or r - l + 1 > minSize: count[s[l]] -= 1 if count[s[l]] == 0: letters -= 1 l += 1 if r - l + 1 == minSize: sub = s[l:l + minSize] substringCount[sub] += 1 ans = max(ans, substringCount[sub]) return ans