<p>Given a string <code>s</code>, return the maximum number of occurrences of <strong>any</strong> substring under the following rules:</p>

<ul>
	<li>The number of unique characters in the substring must be less than or equal to <code>maxLetters</code>.</li>
	<li>The substring size must be between <code>minSize</code> and <code>maxSize</code> inclusive.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aababcaab&quot;, maxLetters = 2, minSize = 3, maxSize = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> Substring &quot;aab&quot; has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaaa&quot;, maxLetters = 1, minSize = 3, maxSize = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> Substring &quot;aaa&quot; occur 2 times in the string. It can overlap.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= maxLetters &lt;= 26</code></li>
	<li><code>1 &lt;= minSize &lt;= maxSize &lt;= min(26, s.length)</code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        '''
        For each size from minSize -> maxSize, do a linear rolling hash algorithm and count substring count
        '''

        AlPHA = 27
        MOD = 10**9 + 7
        def get_index(c):
            return ord(c) - ord('a') + 1
        max_count = 0
        for substring_length in range (minSize, maxSize+1):
            counts = Counter()

            char_counts = Counter()
            s_hash = 0
            # Do the rolling hash and update counts
            for i in range (len(s)):
                s_hash = s_hash * AlPHA + get_index(s[i])
                char_counts[s[i]] += 1

                if i >= substring_length:
                    # Lets do the sliding window
                    to_remove = s[i-substring_length]
                    # print(f"Before: {s_hash}")
                    s_hash -= (get_index(to_remove) * (AlPHA**(substring_length)))
                    # print(f"After: {s_hash}")
                    char_counts[to_remove] -= 1
                    if char_counts[to_remove] == 0:
                        char_counts.pop(to_remove)

                s_hash %= MOD

                # print(f"Hash of {s[max(0, i-substring_length+1):i+1]}: {s_hash}")
                
                if i >= substring_length-1 and len(char_counts) <= maxLetters:
                    counts[s_hash] +=1 
            
            if len(counts) > 0:
                max_count = max(max_count, max(counts.values()))
        return max_count
29800