Welcome to Subscribe On Youtube

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) { ss.add(t.charAt(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 } 
  • function maxFreq(s: string, maxLetters: number, minSize: number, maxSize: number): number { const cnt = new Map<string, number>(); let ans = 0; for (let i = 0; i < s.length - minSize + 1; ++i) { const t = s.slice(i, i + minSize); const ss = new Set(t.split('')); if (ss.size <= maxLetters) { cnt.set(t, (cnt.get(t) || 0) + 1); ans = Math.max(ans, cnt.get(t)!); } } return ans; }

All Problems

All Solutions