# 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.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

# Solution

Approach 1: use sliding window to lock down substrings with at most k unique chars, then generate substrings that satisfies the rules, and use a counter to count the occurences.

Approach 2: shorter substrings have higher occurences than longer ones, so only care about finding substrings whose size == minSize.

# Code (Python)

Approach 1:

    def maxFreq(self, s: str, k: int, minSize: int, maxSize: int) -> int:
        # idea: use sliding window to lock down substrings with at most k unique chars, then generate substrings that satisfies the rules, and use a counter to count the occurences
        occurences = {}
        
        # solves this problem: find longest substrings that has k unique chars
        window = {}
        left = 0
        for right in range(len(s)):
            if s[right] not in window:
                window[s[right]] = 0
            window[s[right]] += 1
            while len(window) > k:
                window[s[left]] -= 1
                if window[s[left]] == 0:
                    window.pop(s[left])
                left += 1

            if right - left + 1 >= minSize:
                # generate all substrings -- they all end with s[right]
                for length in range(minSize, min(maxSize, right - left + 1) + 1):
                    start = right - length + 1
                    substring = s[start:right + 1]
                    if substring not in occurences:
                        occurences[substring] = 0
                    occurences[substring] += 1
        
        return max(occurences.values()) if occurences else 0

Approach 2:

    def maxFreq(self, s: str, k: int, minSize: int, maxSize: int) -> int:
        # need max number of occurences -- shorter substrings have higher occurences than longer ones, so only care about finding substrings whose size == minSize. Use a dictionary/counter to store occurences.
        occurrences = collections.defaultdict(int)
        
        window = {}
        for i in range(minSize):
            if s[i] not in window:
                window[s[i]] = 0
            window[s[i]] += 1
        if len(window) <= k:
            occurrences[s[:minSize]] += 1
        
        left = 0
        for right in range(minSize, len(s)):
            if s[right] not in window:
                window[s[right]] = 0
            window[s[right]] += 1
            window[s[left]] -= 1
            if window[s[left]] == 0:
                window.pop(s[left])
            left += 1
            
            if len(window) <= k:
                occurrences[s[left:right + 1]] += 1
        
        return max(occurrences.values()) if occurrences else 0

Approach 2:

# Code (C++)

Approach 1:

Approach 2: