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

 
Constraints:

1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s only contains lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        

Solutions:
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        count = collections.Counter(s[i : i + minSize] for i in range(0, n - minSize +  1))
        res = 0 
        for k, v in count.items():
            if len(set(k)) <= maxLetters:
                res = max(res, v)
        return res

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        k = minSize
        count = collections.Counter(s[i:i + k] for i in range(len(s) - k + 1))
        return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        k =minSize
        
        count = Counter(s[i:i + k] for i in range(len(s) - k + 1))
        print(count)
        ans=0
        for w in count:
            if len(set(w)) <= maxLetters:
                ans=max(count[w],ans)
        return ans        
        #return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        word_dic = {}
        str_dic = {}
        r_end = 0
        ans = 0
        
        def update_ans(length):
            if length >= minSize:
                return min(length,maxSize) - minSize + 1
            return 0
        
        for i in range(len(s)):
            while (r_end<len(s)):
                ch = s[r_end]
                if ch in list(word_dic.keys()):
                    word_dic[ch] += 1
                else:
                    if len(list(word_dic.keys())) < maxLetters:
                        word_dic[ch] = 1
                    else:
                        break
                r_end += 1
            for j in range(minSize,min(maxSize,r_end-i) + 1):
                subs = s[i:i+j]
                if subs not in str_dic:
                    str_dic[subs] = 1
                else:
                    str_dic[subs] += 1
            word_dic[s[i]] -= 1
            if word_dic[s[i]] == 0:
                del word_dic[s[i]]
        if not bool(str_dic):
            return 0
        else:
            return max(str_dic.values())


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        seen = defaultdict(lambda : 0)
        m = defaultdict(lambda : 0)
        left = 0
        
        for i in range(len(s)):
            m[s[i]] += 1
            
            while(len(m) > maxLetters or i-left+1 > maxSize):
                m[s[left]] -= 1
                if m[s[left]] == 0:
                    m.pop(s[left])
                left += 1        
            
            
            temp = left
            while i-temp+1 >= minSize:
                seen[s[temp:i+1]] += 1
                temp += 1
                    
        if not seen:
            return 0
        return max(list(seen.values()))

import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        T = lambda: collections.defaultdict( T )
        trie , res = T( ) , 0
        data = [ [ trie , set( ) ] for _ in range( len( s ) - minSize + 1 ) ]
        for i in range( minSize ) :
            for j in range( len( s ) - minSize + 1 ) :
                c = s[i+j]
                cur = data[j]
                cur[1].add(c)
                if i == minSize - 1 and len( cur[ 1 ] ) <= maxLetters :
                    cur[0][c].setdefault( '#' , 0 )
                    cur[0][c]['#'] += 1
                    res = max( res , cur[ 0 ][ c ][ '#' ] )
                cur[ 0 ] = cur[0][c]
        return res

from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        letdict = defaultdict(int)
        subdict = defaultdict(int)
        uniquecount = 0
        start = end = 0
        n = len(s)
        
        while end < n:
            val = s[end]
            letdict[val] += 1
            if letdict[val] == 1:
                uniquecount += 1
            
            while uniquecount > maxLetters or ((end-start)+1) > maxSize:
                val = s[start]
                letdict[val] -= 1
                if letdict[val] == 0:
                    uniquecount -= 1
                start += 1
                
            tstart = start
            while ((end-tstart)+1) >= minSize:
                subdict[s[tstart:end+1]] += 1
                tstart += 1

            end += 1
        if not subdict:
            return 0
        return subdict[max(subdict, key = lambda x: subdict[x])]

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        from collections import defaultdict
        cnt=defaultdict(int)
        for i in range(minSize-1,len(s)):
            low1=i-minSize+1
            low2=i-maxSize+1
            seen1=set()
            seen2=set()
            for k in range(low1,i+1):
                if s[k] not in seen1:
                    seen1.add(s[k])
            if low2>=0 and low1!=low2:
                for k in range(low2,i+1):
                    if s[k] not in seen2:
                        seen2.add(s[k])
                if len(seen2)<=maxLetters:
                    cnt[s[low2:i+1]]+=1
            if len(seen1)<=maxLetters:
                cnt[s[low1:i+1]]+=1
            
        if list(cnt.values()):
            return max(cnt.values())
        return 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        if len(s) < minSize:
            return 0
        
        occur = {}
        l,r=0, minSize
        
        while r <= len(s):
            sub = s[l:r]
            
            if occur.get(sub) is None:
                distinct = set(sub)
                if len(distinct) <= maxLetters:
                    occur[sub] = 1
            else:
                occur[sub]+=1
                
            l += 1
            r += 1
            
        return max(occur.values()) if len(occur) >0 else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        from collections import defaultdict
        res = 0
        valid_str_freq = defaultdict(int)
        window_letter = {}
        left = 0
        right = 0
        for right in range(0, len(s), 1):
            # print(left, right)
            for i in range(left, right, 1):
                if right - i < minSize:
                    break
                valid_str = s[i:right]
                # print(i, right, valid_str)
                valid_str_freq[valid_str] += 1
                res = max(res, valid_str_freq[valid_str])

            # add right
            if s[right] not in window_letter:
                window_letter[s[right]] = 1        
            else:
                window_letter[s[right]] += 1
            
            # check left
            while (len(window_letter) > maxLetters
                or right - left + 1 > maxSize
            ):
                window_letter[s[left]] -= 1
                if window_letter[s[left]] == 0:
                    del window_letter[s[left]]    
                left += 1
        right += 1
        for i in range(left, right, 1):
            if right - i < minSize:
                break
            valid_str = s[i:right]
            # print(i, right, valid_str)
            valid_str_freq[valid_str] += 1
            res = max(res, valid_str_freq[valid_str])
        return res
                        
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        res = collections.Counter()
        b=0
        cc = collections.Counter()
        
        for e in range(len(s)):
            cc[s[e]] += 1
            
            while len(cc)>maxLetters or e-b+1>maxSize:
                cc[s[b]] -= 1
                if cc[s[b]]==0: cc.pop(s[b])
                b += 1
            i=b
            while e-i+1>=minSize:
                res[s[i:e+1]] += 1
                i += 1
        # print(res)
        return res.most_common(1)[0][1] if res else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        d = defaultdict(int)
        for i in range(len(s)-minSize+1):
            letters = set(s[i:i+minSize-1])
            for j in range(minSize, min(maxSize, len(s)-i)+1):
                letters.add(s[i+j-1])
                if len(letters) > maxLetters:
                    break
                d[s[i:i+j]] += 1
        return max(d.values()) if d else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = defaultdict(lambda: 0)
        m = ''
        n = len(s)
        for i in range(n - minSize + 1):
            end = i + minSize
            unique = set(s[i:end])
            while end <= n:
                unique.add(s[end - 1])
                if len(unique) > maxLetters:
                    break
                cur = s[i:end]
                freq[cur] += 1
                if freq[cur] > freq[m]:
                    m = cur
                end += 1
        return freq[m]


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = defaultdict(lambda: 0)
        m = ''
        uniques = defaultdict(lambda: set())
        n = len(s)
        for i in range(n - minSize + 1):
            end = i + minSize
            unique = set(s[i:end])
            while end <= n:
                unique.add(s[end - 1])
                if len(unique) > maxLetters:
                    break
                cur = s[i:end]
                freq[cur] += 1
                if freq[cur] > freq[m]:
                    m = cur
                end += 1
        return freq[m]


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        seen = Counter()
        cnt = Counter()
        j = 0
        for i, ss in enumerate(s):
            cnt[ss] += 1
            while len(cnt) > maxLetters and j <= i:
                cnt[s[j]] -= 1
                if not cnt[s[j]]:
                    del cnt[s[j]]
                j += 1
            k = j
            while i - k + 1 >= minSize:
                if i - k + 1 <= maxSize:
                    seen[s[k: i + 1]] += 1
                k += 1
        return max(seen.values()) if seen else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ret = defaultdict(int)
        for i in range(len(s)):
            temp = ''
            char = set()
            for j in range(i, len(s)):
                temp = temp + s[j]
                char.add(s[j])
                if len(char) <= maxLetters and minSize <= len(temp) <= maxSize:
                    ret[temp] += 1
                elif len(char) > maxLetters or len(temp) > maxSize:
                    break

        if len(ret) == 0:
            return 0
        return max(ret.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n=len(s)
        d=collections.defaultdict(int)
        for i in range(0,n-minSize+1):
            temp=s[i:i+minSize]
            c=set(temp)
            if len(c)<=maxLetters:
                d[temp]+=1
        return max(d.values()) if d else 0


from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        mx_count = 0
        
        def create_dct(size, mx_count):
            dct = defaultdict(int)
        
            i = 0
            j = size - 1

            while j < len(s):

                temp = []
                temp_dict = defaultdict(int)

                flag = True
                for x in range(i, j+1):
                    temp.append(s[x])
                    temp_dict[s[x]] += 1
                    if len(temp_dict) > maxLetters:
                        flag = False
                        break

                i += 1
                j += 1

                if not flag:
                    continue
                
                tmp_string = ''.join(temp)
                dct[tmp_string] += 1
                
                if dct[tmp_string] > mx_count:
                    mx_count = dct[tmp_string]
            
            return mx_count
                    
        mx_count = create_dct(minSize, mx_count)
        mx_count = max(create_dct(maxSize, mx_count), mx_count)
        
        return mx_count
        
        
        
            
            
            
            
            
            
                
                
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        c = Counter()
        i = 0
        letterlen = 0
        maxSize = maxSize+1 if maxSize==minSize else maxSize
        ans = Counter()
        for j, v in enumerate(s):
            c[v] += 1
            if c[v] == 1:
                letterlen += 1
            while letterlen > maxLetters:
                x = s[i]
                c[x] -= 1
                if c[x] == 0:
                    letterlen -= 1
                i += 1
            #print(i,j)
            for l in range(minSize,maxSize):
                beg = j-l +1
                #print(i,j,beg)
                if beg >= i:
                    ans[s[beg:j+1]] += 1
        #print(ans)
        return max(ans.values()) if ans else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = 0
        n = len(s)
        count = Counter()
        
        for i in range(n - minSize + 1):
            
            r = i + minSize
            seen = {c for c in s[i:r]}
            unique = len(seen)
            while unique <= maxLetters and r <= n and r - i <= maxSize:
                if s[r - 1] not in seen:
                    unique += 1
                    seen.add(s[r-1])
                count[s[i:r]] += 1
                r += 1
                
        return max(count.values()) if count else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if minSize > len(s): return 0
        left= 0
        candidates = Counter()
        while left <= len(s) - minSize:
            right = left + minSize
            count = set(s[left:right])
            while right <= len(s) and right-left <= maxSize and len(count) <= maxLetters:
                if right < len(s):
                    count.add(s[right])
                candidates[s[left:right]] += 1
                right += 1                
            left += 1
        if not candidates:
            return 0
        return max(candidates.values())


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        feq = collections.Counter()
        
        N = len(s)
        for i in range(N):
            letters = set([c for c in s[i : i + minSize - 1]])
            for j in range(minSize, maxSize + 1):
                k = i + j
                if k > N:
                    break
                letters.add(s[k - 1])
                if len(letters) > maxLetters:
                    break
                feq[s[i:k]] += 1
        
        return max(feq.values()) if list(feq.values()) else 0
                
                

                
                
                


class Solution:
    def maxFreq(self, s: str, mxl: int, mns: int, mxs: int) -> int:
        freq = collections.Counter()
        for i in range(mns, len(s)+1):
            for j in range(mxs-mns+1):
                if i + j > len(s):
                    break
                curr = s[i-mns:i+j]
                if len(set(curr)) > mxl:
                    break
                freq[curr] += 1
        return max(freq.values() or [0])

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        from collections import defaultdict
        letters = defaultdict(int)
        res = 0
        if len(s) < minSize:
            return 0
        i = 0
        j = 0
        unique = 0
        counter = defaultdict(int)
        while i < len(s):
            if letters[s[i]] == 0:
                unique += 1
            letters[s[i]] += 1
            
            while j < i and unique > maxLetters:
                letters[s[j]] -= 1
                if letters[s[j]] == 0:
                    unique -= 1
                j += 1
            j_tmp = j
            unique_tmp = unique
            letters_tmp = letters.copy()
            while unique_tmp <= maxLetters and (minSize <= (i - j_tmp + 1)):
                if (i - j_tmp + 1) > maxSize:
                    j_tmp+=1
                    continue
                counter[s[j_tmp:i+1]] += 1
                #print(f'{s[j_tmp:i+1]} {counter} {i} {j_tmp}')
                letters_tmp[s[j_tmp]] -= 1
                if letters_tmp[s[j_tmp]] == 0:
                    unique_tmp -= 1
                j_tmp += 1
                #print(f'i {i} j {j} unique {unique} {s[j:i+1]} letters {letters},res {res}, len {i-j+1}, {counter}')
            i += 1
        if len(counter.values()) == 0:
            return 0
        
        return max(counter.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        start = 0
        end = minSize
        counts = {}
        res = 0
        
        while start <= len(s)-minSize:
            item = s[start:end]
            counts[item] = counts.get(item, 0) + 1
            
            start += 1
            end += 1
            
        for i in counts:
            if self.countUnique(i) <= maxLetters:
                res = max(res, counts[i])
                  
        return res
        
    def countUnique(self, s):
        return len(set(s))

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        ln_s    =   len(s);
        ans =   0;
        seen    =   Counter();
        
        for i in range( ln_s):
            
            set_buff    =   set(s[i:i+minSize]);
            for j in range(i+minSize-1, min(ln_s, i+maxSize)):
                
                buff    =   s[i:j+1];
                set_buff.add(   s[j]);
                
                if len(set_buff) > maxLetters:  break;
                
                seen[buff] += 1;
                
                ans =   max(    ans, seen[buff]);
        
        return ans;

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        subs = {}
        i = j = 0
        chars = {}
        while i < len(s):
            if  j < len(s) and (s[j] in chars or len(chars) < maxLetters):
                if s[j] not in chars:
                    chars[s[j]] = 0
                chars[s[j]] += 1
                j += 1
            else:
                for k in range(i+minSize, min(i+maxSize, j)+1):
                    sub = s[i:k]
                    if sub not in subs:
                        subs[sub] = 0
                    subs[sub] += 1
                    
                chars[s[i]] -= 1
                if chars[s[i]] == 0:
                    del chars[s[i]]
                i += 1
        return max(list(subs.values()) or [0])


class Solution:
    def maxFreq(self, s, maxLetters, minSize, maxSize):
        if minSize > len(s):
            return 0
            
        left = 0
        right = minSize - 1
        words = {}
        
        while left < len(s) - minSize + 1:
            word = s[left:right+1]
            while right < len(s) and right - left < maxSize and len(set(word)) <= maxLetters:
                if word not in words:
                    words[word] = 0
                words[word] += 1

                right += 1
                if right < len(s):
                    word += s[right]
            
            left += 1
            right = left + minSize - 1
        
        maxOccurences = 0
        for word in words:
            maxOccurences = max(maxOccurences, words[word])
        
        return maxOccurences

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        d = dict()
        n = len(s)
        for i in range(n):
            j = i
            st = set()
            l = 0
            while j<min(n,i+maxSize) and l<=maxLetters:
                if s[j] not in st:
                    l+=1
                    st.add(s[j])
                x = s[i:j+1]
                ln = j-i+1
                #print(x,ln)
                if ln>=minSize and ln<=maxSize and l<=maxLetters:
                    if x in d:
                        d[x]+=1
                    else:
                        d[x]=1
                j+=1
        if d==dict():
            return 0
        return max(list(d.values()))
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        N = len(s)
        d1 = {}
        maxval = 0
        for i in range(N-minSize+1):
            d = {}
            for j in range(i,i+minSize):
                if(s[j] not in d):
                    d[s[j]] = 1
                else:
                    d[s[j]] += 1
            if(len(d)<=maxLetters):
                if(s[i:i+minSize] not in d1):
                    d1[s[i:i+minSize]] = 1
                else:
                    d1[s[i:i+minSize]] += 1
                maxval = max(maxval,d1[s[i:i+minSize]])
            else:
                continue
            for j in range(i+minSize, min(i+maxSize,N)):
                if(s[j] not in d):
                    d[s[j]] = 1
                else:
                    d[s[j]] += 1
                if(len(d)<=maxLetters):
                    if(s[i:j+1] not in list(d1.keys())):
                        d1[s[i:j+1]] = 1
                    else:
                        
                        d1[s[i:j+1]] += 1
                    maxval = max(maxval,d1[s[i:j+1]])
                else:
                    break       
        return maxval


import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ans , freq_subs , n = collections.defaultdict( int ) , 0 , len( s )
        for i in range( n - minSize + 1 ) :
            for j in range( i + minSize  , n + 1 ) :
                if len( set( s[ i : j ] ) ) <= maxLetters :
                    if s[i:j] in ans :
                        ans[ s[i:j] ] += 1
                        freq_subs = max( freq_subs , ans[s[i:j]] )
                    else :
                        ans[s[i:j]] = 1
                        freq_subs = max( freq_subs , 1 )
                else :
                    break
        return freq_subs

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = Counter()
        for leftInd, char in enumerate(s):
            seen = set([])
            for rightInd in range(leftInd, leftInd + maxSize):
                if rightInd > len(s) - 1:
                    break
                seen.add(s[rightInd])
                if len(seen) > maxLetters:
                    break
                if maxSize >= rightInd - leftInd + 1 >= minSize:
                    freq[s[leftInd:rightInd + 1]] += 1
        ret = 0
        for key, val in freq.items():
            ret = max(ret, val)
        return ret

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cache=collections.defaultdict(int)
        for i in range(len(s)+1-minSize):
            if len(set(s[i:i+minSize]))<=maxLetters:
                cache[s[i:i+minSize]]+=1
        res=0
        for k,v in list(cache.items()):
            res=max(res,v)
        return res
                
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        d=defaultdict(int)
        s=list(s)
        n=len(s)

        for i in range(n-minSize+1):
            for j in range(i+minSize,min(i+maxSize+1,n+1)):
                if len(set(s[i:j]))<=maxLetters:
                    d[tuple(s[i:j])]+=1
                   
                else:
                    break
        if not d:
            return 0
        return max(d.values())


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if minSize > len(s):
            return 0
        maxCount = 0
        seenSubstrs = Counter()
        for i in range(len(s)):
            letterSet = set()
            for j in range(i, i + minSize - 1):
                if j >= len(s):
                    break
                letterSet.add(s[j])
                if len(letterSet) > maxLetters:
                    break
            if len(letterSet) > maxLetters:
                continue
            for j in range(i+minSize-1, i+maxSize+1):
                if j >= len(s):
                    break
                letterSet.add(s[j])
                if len(letterSet) > maxLetters:
                    break
                seenSubstrs[s[i:j+1]] += 1
                maxCount = max(seenSubstrs[s[i:j+1]], maxCount)
        return maxCount


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sub = dict()

        for i in range(len(s) - minSize + 1):
            d = dict()
            for k in range(i, i + minSize):
                if s[k] in d:
                    d[s[k]] += 1
                else:
                    d[s[k]] = 1

            if len(d) <= maxLetters:
                phrase = s[i:i+minSize]
                if phrase in sub:
                    sub[phrase] += 1
                else:
                    sub[phrase] = 1
            else:
                continue

            for j in range(i + minSize, i + maxSize):
                if j < len(s):
                    if len(d) <= maxLetters:
                        phrase = s[i:j+1]
                        if phrase in sub:
                            sub[phrase] += 1
                        else:
                            sub[phrase] = 1
                    else:
                        break

                    if s[j] in d:
                        d[s[j]] += 1
                    else:
                        d[s[j]] = 1

        if not sub:
            return 0
        return max(sub.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        res_dict = collections.defaultdict(int)
        
        for lidx in range(n-minSize+1):
            lval = lidx+minSize
            rval = min(n,lidx+maxSize+1)
            for ridx in range(lval, 1+rval):
                counts = set(s[lidx:ridx])
                if len(counts) <= maxLetters:
                    res_dict[s[lidx:ridx]] += 1
                else: 
                    break
        
        return max(res_dict.values()) if res_dict else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        def valid(sub):
            seen = set()
            for c in sub: seen.add(c)
            return len(seen)
            
        counts = dict()
        start = 0
        while start < len(s):
            end = start+minSize
            while end <= len(s) and end <= start + maxSize:
                sub = s[start:end]
                if sub in counts:
                    counts[sub] += 1
                else:
                    num_letters = valid(sub)
                    if num_letters <= maxLetters:
                        counts[sub] = 1
                    else:
                        break
                end += 1
            start += 1
        
        l = list(counts.values())
        if len(l) == 0: return 0
        return max(l)
            
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        all_substrings = {}
        max_letters = maxLetters
        min_size = minSize
        max_size = maxSize
        _s = s
        ll = len(_s)
        for i in range(min_size, max_size + 1):
            for j in range(ll - i + 1):
                ss = _s[j:j+i]
                if max_letters >= min_size or len(set(ss)) <= max_letters:
                    if ss not in all_substrings:
                        all_substrings[ss] = 1
                    else:
                        all_substrings[ss] += 1
        return max(all_substrings.values()) if len(all_substrings) > 0 else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sol = {}
        for i in range(len(s) - minSize + 1):
            count = set()
            length = 0
            for j in range(minSize - 1):
                length += 1
                c = s[i+j]
                if c not in count:
                    count.add(c)
            while length < maxSize and (i + length) < len(s):
                c = s[i + length]
                if c not in count:
                    count.add(c)
                if len(count) <= maxLetters:
                    substring = s[i: i+length+1]
                    if substring in sol:
                        sol[substring] += 1
                    else:
                        sol[substring] = 1
                length += 1
        maximum = 0
        for substring in sol:
            if sol[substring] > maximum:
                maximum = sol[substring]
        return maximum

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    
        cur_soln = {s[:minSize]: 1}
        
        for end in range(minSize, len(s)):
            for start in range(end-minSize+1, max(-1, end-maxSize), -1):
                subs = s[start:end+1]
                cur_soln[subs] = cur_soln.get(subs, 0) + 1

        cur_best = 0
        for s, cnt in list(cur_soln.items()):
            if cnt > cur_best and len(set(s)) <= maxLetters:
                cur_best = cnt
        return cur_best
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        count = collections.Counter()
        
        for i in range(len(s) - minSize + 1):
            t = s[i:minSize+i]
            if len(set(t)) <= maxLetters:
                count[t] += 1
                
                
                
        if count:
            return max(count.values())
        else:
            return 0 

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        maxcount = 0
        visited = {}
        for i in range(len(s)):
            for j in range(minSize, minSize+1):
                now = s[i:i+j]
                if now in visited:
                    continue
                    
                visited[now] = 1
                if i + j > len(s):
                    break
                    
                nowset = set(now)
                if len(nowset) > maxLetters:
                    break
                
                count = 1
                start = i+1
                while(start < len(s)):
                    pos = s.find(now, start)
                    if pos != -1:
                        start = pos + 1
                        count += 1
                    else:
                        break
                    
                maxcount = max(maxcount, count)
        
        return maxcount

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrings = defaultdict(int)
        for gap in range(minSize, maxSize + 1):
            for start in range(len(s) - gap + 1):
                end = start + gap
                substrings[s[start:end]] += 1
        max_ = 0
        for substring, times in substrings.items():
            if times > max_ and len(set(substring)) <= maxLetters:
                max_ = times
        return max_

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if maxLetters == 0:
            return 0
        sw = collections.defaultdict(int)
        substrings = collections.defaultdict(int)
        l = 0
        res = 0
        for r, ch in enumerate(s):
            sw[ch] += 1
            while l <= r and len(sw) > maxLetters:
                chL = s[l]
                sw[chL] -= 1
                if sw[chL] == 0:
                    del sw[chL]
                l += 1
            #print(r, r + 1 - maxSize, r + 1 - minSize + 1)
            #print(l, r)
            for j in range(r + 1 - maxSize, r + 1 - minSize + 1):
                if j < l:
                    continue
                substrings[s[j : r + 1]] += 1
                res = max(res, substrings[s[j : r + 1]])
            #print(substrings)
        return res
        
        #l r


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        maxi = 0
        
        for index in range(minSize, maxSize + 1):
            result = self.getAllSubstringsWithRules(s, maxLetters, index)
            
            if result > maxi:
                maxi = result
                
        return maxi
    
    def getAllSubstringsWithRules(self, s, maxLetters, size):
        length = len(s)
        letters = {}
        subStrings = {}
        
        for index in range(size):
            letter = s[index]
            
            if letter not in letters:
                letters[letter] = 0
                
            letters[letter] += 1
            
        if len(letters) <= maxLetters:
            subStrings[s[:size]] = 1
            
        for index in range(size, length):
            letterToRemove = s[index - size]
            letters[letterToRemove] -= 1
            
            if letters[letterToRemove] == 0:
                del letters[letterToRemove] 
                
            letterToAdd = s[index]
            
            if letterToAdd not in letters:
                letters[letterToAdd] = 0
                
            letters[letterToAdd] += 1
            
            if len(letters) <= maxLetters:
                string = s[index - size + 1:index + 1]
                if string not in subStrings:
                    subStrings[string] = 0
                    
                subStrings[string] += 1
                
        if not subStrings:
            return 0
                
        return max(subStrings.values())
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        cnt = defaultdict(int)
        
        for i in range(n):
            now = ''
            se = set()
            
            for j in range(maxSize):
                if i+j>=n:
                    break
                    
                now += s[i+j]
                se.add(s[i+j])
                
                if len(se)<=maxLetters and len(now)>=minSize:
                    cnt[now] += 1
        
        ans = 0
        
        for v in cnt.values():
            ans = max(ans, v)
        
        return ans

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sol = {}
        for i in range(len(s) - minSize + 1):
            count = {}
            length = 0
            for j in range(minSize - 1):
                length += 1
                c = s[i+j]
                if c in count:
                    count[c] += 1
                else:
                    count[c] = 1
            while length < maxSize and (i + length) < len(s):
                c = s[i + length]
                if c in count:
                    count[c] += 1
                else:
                    count[c] = 1
                if len(count) <= maxLetters:
                    substring = s[i: i+length+1]
                    if substring in sol:
                        sol[substring] += 1
                    else:
                        sol[substring] = 1
                length += 1
        maximum = 0
        for substring in sol:
            if sol[substring] > maximum:
                maximum = sol[substring]
        return maximum

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt=collections.Counter()
        for i in range (len(s)-minSize+1):
            sub=s[i:i+minSize]
            if len(set(sub))<=maxLetters:
                cnt[sub]+=1
        return max(cnt.values()) if cnt else 0    
                    


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sol = {}
        for i in range(len(s) - minSize + 1):
            count = set()
            length = 0
            while length < maxSize and (i + length) < len(s):
                c = s[i + length]
                if c not in count:
                    count.add(c)
                length += 1
                # print(s[i: i+length+1])
                if len(count) <= maxLetters and length >= minSize:
                    substring = s[i: i+length]
                    if substring in sol:
                        sol[substring] += 1
                    else:
                        sol[substring] = 1
        maximum = 0
        for substring in sol:
            if sol[substring] > maximum:
                maximum = sol[substring]
        return maximum

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
                
        counts = {} # string -> number 
        
        for current_size in range(minSize, maxSize + 1): 
            window = {}
            for i in range(current_size-1): 
                c = s[i]
                window[c] = window.get(c, 0) + 1 
            
            for i in range(current_size-1, len(s)):
                start = i - current_size

                # add current 
                c = s[i]
                window[c] = window.get(c, 0) + 1 
                
                # remove tail
                if start >= 0:
                    c = s[start]
                    window[c] -= 1 
                    if window[c] == 0:
                        del window[c]
                    
                # check
                if len(window) <= maxLetters: 
                    sub = s[start+1:i+1]
                    counts[sub] = counts.get(sub, 0) + 1 
                    
        # print(counts)
        return max(counts.values()) if len(counts) else 0 


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = {}
        for outer in range(0,len(s)):
            if minSize + outer > len(s): break
            substring = s[outer:minSize+outer]
            while len(substring) <= maxSize and len(set(substring))<=maxLetters:
                if dic.get(substring): 
                    dic[substring] += 1
                else: dic[substring] = 1
                newIndex = outer + len(substring) + 1
                if not newIndex > len(s):
                    substring = s[outer:newIndex]
                else: break
        if dic:
            maxKey = max(dic,key=lambda key: dic[key])
            return dic[maxKey]
        else: return 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        for i in range(minSize, maxSize+1):
            max_freq = self.maxFreqSetSize(s, maxLetters, i)
            if max_freq > 0:
                return max_freq
        return 0
        
    def maxFreqSetSize(self, s, maxLetters, windowSize):
        valid_substrings = set()
        maxFreq = 0
        for i in range(len(s)-windowSize):
            substring = s[i:i+windowSize]
            if substring in valid_substrings:
                continue
            unique_letters = set()
            for k in range(windowSize):
                letter = s[i+k]
                unique_letters.add(letter)
            if len(unique_letters) > maxLetters:
                continue
            frequency = 1
            pos = i + 1
            while pos > -1:
                new_pos = s[pos:].find(substring)
                if new_pos == -1:
                    break
                frequency += 1
                pos += new_pos + 1
                            
            if frequency > maxFreq:
                maxFreq = frequency
            valid_substrings.add(substring)
        return maxFreq

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        
        mymap = collections.defaultdict(int)
        st, j, n = 0, 0, len(s)
#         charmap = collections.defaultdict(int)
        
#         for i in range(st, st+minSize-1):
#             charmap[s[i]] += 1
#         # print(charmap)
        while st + minSize <= n:
            # print (st)
            count = collections.Counter(s[st:st+minSize-1])
            for j in range(st+minSize-1, st+maxSize):
                
                if j >= n:
                    break
                    
                count[s[j]] += 1
                if len(count) <= maxLetters:
                    mymap[s[st:j+1]] += 1
                
                
                
                
                
#                 print(j, s[st:])
#                 if j >= n:
#                     break
                    
#                 charmap[s[j]] += 1
#                 if len(charmap) <= maxLetters:
#                     mymap[s[st:j+1]] += 1
                
                 
#             charmap[s[st]] -= 1
#             if charmap[s[st]] <= 0:
#                 charmap.pop(s[st])
            st += 1
                    
        # ans = 0  
        maxval = max(list(mymap.values()) or [0])
        # for key in mymap:
        #     if mymap[key] == maxval:
        #         ans += 1
                
        return maxval
        # print(mymap)
        
        
        
        
        
        
        
        
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        validWords = {}
        for i in range(0, len(s)):
            for j in range(i + minSize - 1, min(i + maxSize, len(s))):
                ss = s[i:j + 1]
                if len(set(ss)) <= maxLetters:
                    if ss in validWords:
                        validWords[ss] += 1
                    else:
                        validWords[ss] = 1

        # print(\"valid: \", validWords)
        if validWords:
            all_values = validWords.values()
            return max(all_values)
        else:
            return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        mymap = collections.defaultdict(int)
        st, j, n = 0, 0, len(s)
        while st + minSize <= n:
            # print (st)
            count = collections.Counter(s[st:st+minSize-1])
            for j in range(st+minSize-1, st+maxSize):
                if j >= n:
                    break
                count[s[j]] += 1
                if len(count) <= maxLetters:
                    mymap[s[st:j+1]] += 1
            st += 1
        maxval = max(list(mymap.values()) or [0])
        return maxval
        
        
        
#         mymap = collections.defaultdict(int)
#         st, j, n = 0, 0, len(s)
# #         charmap = collections.defaultdict(int)
        
# #         for i in range(st, st+minSize-1):
# #             charmap[s[i]] += 1
# #         # print(charmap)
#         while st + minSize <= n:
#             # print (st)
#             count = collections.Counter(s[st:st+minSize-1])
#             for j in range(st+minSize-1, st+maxSize):
                
#                 if j >= n:
#                     break
                    
#                 count[s[j]] += 1
#                 if len(count) <= maxLetters:
#                     mymap[s[st:j+1]] += 1
                
                
                
                
                
# #                 print(j, s[st:])
# #                 if j >= n:
# #                     break
                    
# #                 charmap[s[j]] += 1
# #                 if len(charmap) <= maxLetters:
# #                     mymap[s[st:j+1]] += 1
                
                 
# #             charmap[s[st]] -= 1
# #             if charmap[s[st]] <= 0:
# #                 charmap.pop(s[st])
#             st += 1
                    
#         # ans = 0  
#         maxval = max(mymap.values() or [0])
#         # for key in mymap:
#         #     if mymap[key] == maxval:
#         #         ans += 1
                
#         return maxval
#         # print(mymap)
        
        
        
        
        
        
        
        
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        maxOcc = 0
        strOcc = {}
        
        for i in range(minSize, maxSize + 1):
            charFreq = {}
            sub = s[:i]
            uniqueChar = 0
            
            for c in sub:
                if c not in charFreq:
                    charFreq[c] = 0
                    uniqueChar += 1
                charFreq[c] += 1
            
            if uniqueChar <= maxLetters:
                if sub not in strOcc:
                    strOcc[sub] = 0
                strOcc[sub] += 1
                maxOcc = max(maxOcc, strOcc[sub])
            
            for j in range(i, len(s)):
                outC = sub[0]
                inC = s[j]
                
                charFreq[outC] -= 1
                if charFreq[outC] == 0:
                    uniqueChar -= 1
                    del charFreq[outC]
                    
                if inC not in charFreq:
                    charFreq[inC] = 0
                    uniqueChar += 1
                charFreq[inC] += 1
                
                sub = sub[1:] + inC
                
                if uniqueChar <= maxLetters:
                    if sub not in strOcc:
                        strOcc[sub] = 0
                    strOcc[sub] += 1
                    maxOcc = max(maxOcc, strOcc[sub])
                    
        return maxOcc
                
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        if n < minSize:
            return 0
        c = collections.Counter()
        for start in range(n - minSize+1):
            temp = s[start:start+minSize]
            tc = collections.Counter(temp)
            if len(tc.keys()) <= maxLetters:
                c[temp] += 1
            else:
                continue
            for i in range(start+minSize,min(n,start + maxSize)):
                tc[s[i]] += 1
                temp += s[i]
                if len(tc.keys()) <= maxLetters:
                    c[temp] += 1
                else:
                    continue
        return max(c.values() or [0])

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substr = defaultdict(int)
        n = len(s)
        unique = set()
        max_freq = 0
        
        for i in range(n - minSize + 1):
            current_str = s[i:i+minSize]
            
            if len(set(current_str)) <= maxLetters:
                substr[current_str] += 1
                max_freq = max(max_freq, substr[current_str])
        
        
        return max_freq

from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrFreq = defaultdict(int)
        charFreq = defaultdict(int)
        curr_substr = []
        
        l = 0
        r = l + minSize - 1
        
        while l < len(s):
            for ch in s[l:r]:
                curr_substr.append(ch)
                charFreq[ch] += 1
                
            while (r - l + 1) <= maxSize and r < len(s):
                charFreq[s[r]] += 1
                curr_substr.append(s[r])
                
                if len(charFreq) <= maxLetters:
                    # print(curr_substr)
                    substrFreq[''.join(curr_substr)] += 1

                r += 1
                
            curr_substr = []
            charFreq = defaultdict(int)
            l += 1
            r = l + minSize - 1
        
        if substrFreq:
            return max(substrFreq.values())
        return 0


import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        finalDict = collections.defaultdict(int)
        for i in range(len(s)):
            for j in range(i + minSize - 1, min(i + maxSize, len(s))):
                substring = s[i:j+1]
                if len(set(substring)) <= maxLetters:
                    finalDict[substring] += 1
                    
    
    
        return max(finalDict.values()) if finalDict else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = {}
        
        for size in range(minSize, maxSize+1):
            for i in range(len(s) - size + 1):
                sub_str = s[i:i+size]
                
                if len(set(sub_str)) > maxLetters: continue
                
                if sub_str in freq:
                    freq[sub_str] += 1
                else:
                    freq[sub_str] = 1
                
        max_freq = 0
        
        for sub_str, cnt in list(freq.items()):
            max_freq = max(max_freq, cnt)
            
        return max_freq


from collections import defaultdict
from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = defaultdict(int)
        for i in range(len(s)):
            for j in range(i + minSize - 1, min(i + maxSize, len(s))):
                sub = s[i:j + 1]
                if len(set(sub)) <= maxLetters:
                    dic[sub] += 1
        if len(dic):
            return max(dic.values())
        else:
            return 0

from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrFreq = defaultdict(int)
        charFreq = defaultdict(int)
        curr_substr = []
        
        l = 0
        r = l + minSize - 1
        
        while l < len(s):
            for ch in s[l:r]:
                curr_substr.append(ch)
                charFreq[ch] += 1
                
            while (r - l + 1) <= maxSize and r < len(s):
                charFreq[s[r]] += 1
                curr_substr.append(s[r])
                
                if len(charFreq) <= maxLetters:
                    # print(curr_substr)
                    substrFreq[''.join(curr_substr)] += 1

                r += 1
                
            curr_substr = []
            charFreq = defaultdict(int)
            l += 1
            r = l + minSize - 1
        
        mval = 0
        mstr = None
        for s, v in substrFreq.items():
            if v > mval:
                mstr = s
                mval = v
        
        return mval

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # sliding window
        res = collections.Counter()
        n = len(s)
        size = minSize
        while size <= maxSize:
            M = collections.defaultdict(int)
            for i, c in enumerate(s):
                if i < size:
                    M[c] += 1
                    continue

                if len(M) <= maxLetters:
                    res[s[i-size:i]] += 1
                
                # slide the window
                M[s[i-size]] -= 1
                if M[s[i-size]] == 0:
                    del M[s[i-size]]
                M[c] += 1
            # check for last one
            if len(M) <= maxLetters:
                res[s[n-size:]] += 1
            
            size += 1
        
        # print(res.most_common(1))
        ans = res.most_common(1)
        if not ans:
            return 0
        else:
            return ans[0][1]
        
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # brute force this damn thing
        
        # 1. all substrings
        freq = defaultdict(int)
        best = 0
        for l in range(minSize, maxSize+1):
            for i in range(len(s)-l+1):
                ss = s[i:i+l]
                # print('substring', ss)
                if len(set(ss)) <= maxLetters:
                    freq[ss] += 1
                    best = max(best, freq[ss])

        # print(freq)
        return best

class Solution:
    def findSubstring(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> str:
        len_s = len(s)
        
        substrings = {}
        for i in range(len_s):
            for j in range(i+minSize, i+maxSize+1):
                if j > len_s:
                    break
                substring = s[i:j] 
                if len(set(substring)) <= maxLetters:
                    if substring not in substrings:
                        substrings[substring] = 0
                    substrings[substring] += 1
                
                
        return substrings
    
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        len_s = len(s)
        if len_s < minSize:
            return 0
        
        substrings = self.findSubstring(s, maxLetters, minSize, maxSize)
        if not substrings:
            return 0
        return max(substrings.values())
            
                    
            


from collections import Counter


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = Counter()
        
        for k in range(minSize, maxSize + 1):
            for i in range(len(s) - k + 1):
                substring = s[i:i + k]
                if len(set(substring)) <= maxLetters:
                    freq[substring] += 1
                    
        return max(freq.values()) if len(freq) > 0 else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        r = 0
        seen = Counter()
        for i in range(minSize, maxSize+1):
            for j in range(i, len(s)+1):
                t = s[j-i:j]
                if len( set(t)) <= maxLetters:
                    # print(s[j-i:j])
                    seen[t] += 1
                    if seen[t] > r:
                        r = seen[t]
        return r

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        count = collections.Counter(s[i:i + minSize] for i in range(len(s) - minSize + 1))
        return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])
        '''
        If a string have occurrences x times,
any of its substring must appear at least x times.

There must be a substring of length minSize, that has the most occurrences.
So that we just need to count the occurrences of all substring with length minSize.'''

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        max_freq = 0
        for l in range(minSize,maxSize+1):
            hmap = {}
            for i in range(len(s)-l+1):
                if len(set(s[i:i+l])) <= maxLetters:
                    if s[i:i+l] in list(hmap.keys()):
                        hmap[s[i:i+l]] += 1
                    else:
                        hmap[s[i:i+l]] = 1
            if list(hmap.keys()):
                max_freq = max(max_freq,max(list(hmap.items()),key=lambda kv: kv[1])[1])
        return max_freq


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        occ, n = collections.defaultdict(int), len(s)
        for i in range(n):
            for j in range(i + minSize - 1, min(i+maxSize, n)):
                sub = s[i:j+1]
                if len(set(sub)) <= maxLetters:
                    occ[sub] += 1
        return max(occ.values(), default = 0)

class Solution:
    def maxFreq(self, s: str, m: int, n: int, ss: int) -> int:
        def getSubStrings(maxLetters:int, minSize: int, maxSize:int):
            for i in range(len(s)):
                for j in range(i+minSize, len(s) + 1):
                    if j - i > maxSize:
                        break
                    sub = s[i:j]
                    if len(set(sub)) <= maxLetters:
                        yield sub
        
        counter = collections.defaultdict(int)
        ret = 0
        for substring in getSubStrings(m, n, ss):
            counter[substring] += 1
            ret = max(ret, counter[substring])
        return ret


class Solution:
  def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    
    toSearch={}
    for size in range(minSize,maxSize+1):
      for i in range(len(s)-size+1):
        S=s[i:i+size]
        letters=len(set(S))
        if letters<=maxLetters:
          if S in toSearch: toSearch[S]+=1
          else: toSearch[S]=1
    #print(toSearch)
    ans=0
    for e in toSearch:
      ans=max(ans,toSearch[e])
    return ans


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt=collections.Counter()
        for size in range(minSize, maxSize+1):
            for i in range(len(s)-size+1):
                sub=s[i:i+size]
                if len(set(sub))<=maxLetters:
                    cnt[sub]+=1
        return max(cnt.values() )   if cnt else 0          
                    


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        occ, n = {} , len(s)
        
        for i in range(n):
            for j in range(i + minSize - 1, min(i + maxSize, n)):
                sub = s[i:j + 1]
                if len(set(sub)) <= maxLetters:
                    occ[sub] = occ.get(sub,0) +1
                    
        return(max(list(occ.values()) or [0]))
#         ans = list(occ.values())
#         ans.sort(reverse=True)
        
#         return(ans[0] if ans else 0)


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        counts = dict()
        
        for i in range(minSize, maxSize+1):
            for j in range(i, len(s)+1):
                curr = s[j-i:j]
                if curr not in counts:
                    if len(set(curr)) <= maxLetters:
                        counts[curr] = 1
                else:
                    counts[curr] += 1                    
        
        if not counts:
            return 0
        else:
            return max(counts.values())


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        possible = dict()
        for winSize in range(minSize, maxSize + 1):
            for winI in range(len(s) - winSize + 1):
                win = s[winI: winI + winSize]
                letters = set(win)
                if len(letters) <= maxLetters:
                    if win in possible:
                        possible[win] += 1
                    else:
                        possible[win] = 1
        # print(possible)
        if possible:
            return max(possible.values())
        else:
            return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        lookup = {}
        
        for size in range(minSize, maxSize + 1):
            for i in range(0, len(s) - size + 1):
                sub_s = s[i:i+size]
                if len(set(sub_s)) <= maxLetters:
                    if sub_s not in lookup:
                        lookup[sub_s] = 0
                    lookup[sub_s] += 1
                
        if not lookup:
            return 0

        return max(lookup.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # brute force this damn thing
        
        # 1. all substrings
        # if it works with greater than minSize, then must work with exactly minSize
        freq = defaultdict(int)
        best = 0
        for i in range(len(s)-minSize+1):
            ss = s[i:i+minSize]
            # print('substring', ss)
            if len(set(ss)) <= maxLetters:
                freq[ss] += 1
                best = max(best, freq[ss])

        # print(freq)
        return best

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        count = defaultdict(int)
        
        for size in range(minSize, maxSize+1):
            
            for i in range(0, len(s)-size+1):
                
                st = s[i:size+i]
                
                if len(set(st)) <= maxLetters:
                    count[st] += 1
        
        if len(count) == 0:
            return 0
        return max(count.values())
                
                
                    
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        SUB_LEN = len(s)
        cache = defaultdict(int)
        for start in range(SUB_LEN):
            
            for end in range(start + minSize-1, min(start + maxSize, SUB_LEN)):
                
                substring = s[start:end+1]
                
               
                if len(set(substring)) <= maxLetters:
                    
                    cache[substring] += 1 
        #print(cache.values())
        return max(cache.values()) if cache else 0
                    


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        # find subs that satisifes rules
        found = collections.defaultdict(int)
        for sl in range(minSize, min(len(s),maxSize)+1):
            for start_index in range(len(s)-sl + 1):
                substring = s[start_index:start_index+sl]
                if len(set(substring)) <= maxLetters:
                    found[substring] += 1
                    
        vals = sorted(found.values())
        if len(vals) == 0: return 0
        return vals[-1]


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        results = 0
        for l in range(minSize,maxSize+1):
            if l<=n:
                maps = {}
                for i in range(n-l+1):
                    subs = s[i:i+l]
                    if len(set(subs))<=maxLetters:
                        try:
                            maps[subs] += 1
                            if maps[subs]>results:
                                results = maps[subs]
                        except KeyError:
                            maps[subs] = 1
                            if maps[subs]>results:
                                results = maps[subs]
        return results


import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrings = []
        for size in range(minSize, maxSize + 1):
            for i in range(len(s)-size+1):
                if len(set(s[i:i+size])) <= maxLetters:
                    substrings.append(s[i:i+size])
        return collections.Counter(substrings).most_common(1)[0][1] if substrings else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        all_substrings = {}
        for i in range(minSize, maxSize + 1):
            for j in range(len(s) - i + 1):
                ss = s[j:j+i]
                if len(set(ss)) <= maxLetters:
                    if ss not in all_substrings:
                        all_substrings[ss] = 0
                    all_substrings[ss] += 1
        if len(all_substrings) > 0:
            return max(all_substrings.values())
        else:
            return 0

from collections import defaultdict
from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = defaultdict(int)
        for i in range(0, len(s) - minSize + 1):
            for j in range(minSize, maxSize + 1):
                if i + j > len(s):
                    break
                cur_str = s[i:i+j]
                unique_letters = set(cur_str)
                if len(unique_letters) > maxLetters:
                    continue
                else:
                    dic[cur_str] += 1
        if len(dic) > 0:
            return max(dic.values())
        else:
            return 0

import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        counter = collections.defaultdict(int)
        for ln in range(minSize,maxSize+1):
            for i in range(0,len(s)-ln+1):
                sub = s[i:i+ln]
                if len(set(sub))<=maxLetters:
                    counter[sub] += 1
        count = [item[1] for item in counter.items()]
                       
        return max(count) if count else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        i = 0
        lst = []
        while i < len(s):
            for j in range(minSize, maxSize+1):
                subs = s[i:i+j]
                
                # check the num of char
                # c = collections.Counter(subs)
                # for char in c:
                #     if c[char] > maxLetters:
                #         continue
                sc = set(subs)
                if len(sc) > maxLetters:
                    continue
                if len(subs)>= minSize and len(subs)<=maxSize and i+j<=len(s):
                    lst.append(subs)
            i+=1

        # check the number of occurence of each subs
        c = collections.Counter(lst)
        maxs = 0
        for subs2 in c:
            maxs = max(c[subs2], maxs)
            
        return maxs
            
        
        

                
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, a: int, b: int) -> int:
        cnt = collections.defaultdict(int)
        for i in range(len(s)-a+1):
            cnt[s[i:i+a]]+=1
        for a, v in sorted(cnt.items(), key = lambda x:x[1], reverse=True):
            if len(set(a))<=maxLetters:return v
        return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        res, occ = 0, collections.defaultdict(int)
        
        for r in range(len(s) - minSize + 1):
            
            sub = s[r:r+minSize]
            
            if len(set(sub)) <= maxLetters:
                
                occ[sub] += 1
                res = max(res, occ[sub])
                
        return(res)

from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        d = defaultdict(int)
        n = len(s)
        
        for i in range(n):
            # (i + minSize - 1, min(i + maxSize, n))
            for j in range(i+minSize-1, min(i+maxSize, n)):
                # print(s[i:j])
                if len(set(s[i:j+1])) <= maxLetters:
                    d[s[i:j+1]]+=1
        # print(d)
        if d:
            return max(d.values())
        return 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
#         minSize <= size <= maxSize
#         uniqu <= maxLetters
        
#         loop from 3 to 4
#         aab abcaab
        
#         aaba
#         to find number of uniques, find the len of the set
        
#         TIME: O(SN^2)
#         SPACE: O(N)
#         abcde length = 5
#               size = 3
        
#         abcde

        ans = 0
        counter = collections.Counter()
        
        for size in range(minSize, maxSize+1):
            for j in range(len(s)-size+1):
                substring = s[j:j+size]
                if len(set(substring)) <= maxLetters:
                    counter[substring]+=1
                    ans = max(ans,counter[substring])
#                     count = 1
#                     for k in range(j+1, len(s)-size+1):
#                         if substring == s[k:k+size]: count += 1
#                     ans = max(ans,count)
        return ans
                    


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        all_substrings = {}
        max_letters = maxLetters
        min_size = minSize
        max_size = maxSize
        _s = s
        max = 0
        for i in range(min_size, max_size + 1):
            for j in range(len(_s) - i + 1):
                ss = _s[j:j+i]
                if len(set(ss)) <= max_letters:
                    if ss not in all_substrings:
                        all_substrings[ss] = 0
                    all_substrings[ss] += 1
                    if all_substrings[ss] > max:
                        max = all_substrings[ss]
        return max

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        cnt = Counter()
        # for size in range(minSize, minSize+1):
        # size = minSize
        # for i in range(len(s)-size+1):
        #     ss = s[i:i+size]
        #     if len(set(ss)) <= maxLetters:
        #         cnt[ss]+=1
        # return max(cnt.values()) if cnt else 0
    
    
    
        # sliding window
        res = collections.Counter()
        size = minSize
        while size <= maxSize:
            for i in range(len(s)-size+1):
                ss = s[i:i+size]
                if len(set(ss)) <= maxLetters:
                    res[ss] += 1
            size += 1
            
        return max(res.values()) if res else 0


class Solution:
    def maxFreq(self, s, maxLetters, minSize, maxSize):
        if minSize > len(s):
            return 0
            
        words = {}
        for size in range(minSize, maxSize + 1):
            left = 0
            right = size - 1
            while right < len(s):
                word = s[left:right + 1]
                if len(set(word)) <= maxLetters:
                    if word not in words:
                        words[word] = 0
                    words[word] += 1
                left += 1
                right += 1
        
        maxOccurences = 0
        for word in words:
            maxOccurences = max(maxOccurences, words[word])
        
        return maxOccurences

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # k = minSize
        # count = collections.Counter(s[i:i + k] for i in range(len(s) - k + 1))
        # return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])
        cnt = Counter()
        for size in range(minSize, maxSize+1):
            for i in range(len(s)-size+1):
                ss = s[i:i+size]
                if len(set(ss)) <= maxLetters:
                    cnt[ss]+=1
        return max(cnt.values()) if cnt else 0
    
    
    
        # sliding window
#         res = collections.Counter()
#         n = len(s)
#         size = minSize
#         while size <= maxSize:
#             M = collections.defaultdict(int)
#             for i, c in enumerate(s):
#                 if i < size:
#                     M[c] += 1
#                     continue

#                 if len(M) <= maxLetters:
#                     res[s[i-size:i]] += 1
                
#                 # slide the window
#                 M[s[i-size]] -= 1
#                 if M[s[i-size]] == 0:
#                     del M[s[i-size]]
#                 M[c] += 1
#             # check for last one
#             if len(M) <= maxLetters:
#                 res[s[n-size:]] += 1
            
#             size += 1
        
#         # print(res.most_common(1))
#         ans = res.most_common(1)
#         if not ans:
#             return 0
#         else:
#             return ans[0][1]


from collections import defaultdict
from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = defaultdict(int)
        for i in range(0, len(s) - minSize + 1):
            for j in range(minSize, maxSize + 1):
                if i + j > len(s):
                    break
                cur_str = s[i:i+j]

                unique_letters = set(cur_str)
                if len(unique_letters) > maxLetters:
                    continue
                else:
                    dic[cur_str] += 1


        res = 0
        for s in dic:
            res = max(res, dic[s])
        return res

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        maxOccurrences = 0
        substrings = dict()
        
        for i in range(minSize, maxSize + 1):
            
            for j in range(len(s)):
                
                if i + j <= len(s):
                    
                    current = s[j:j+i]
                    
                    if len(set(current)) <= maxLetters:
                        
                        if current in substrings:
                            
                            substrings[current] += 1
                        
                        else:
                            
                            substrings[current] = 1
                    
                        if substrings[current] > maxOccurrences:
                            
                            maxOccurrences = substrings[current]
                            
                            
        
        return maxOccurrences

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        dict = {}
        for i in range(len(s)):
            for j in range(i+minSize, i+maxSize+1):
                # check if substr already in dict
                if j <= len(s):
                    substr = s[i:j]
                    if len(set(substr)) <= maxLetters:
                        if substr in dict:
                            dict[substr] += 1
                        else:
                            dict[substr] = 1

        # count max value of dict
        max_count = 0
        for k,v in list(dict.items()):
            max_count = max(max_count, v)

        return max_count
        
        
        # brute force - TLE
#         max_count = 0

#         for i in range(len(s)):
#             for j in range(i+minSize, i+maxSize+1):
#                 if j < len(s):
#                     substr = s[i:j]
#                     # print(\"checking substr: \", substr)
#                     # valid substring length
#                     if len(set(substr)) <= maxLetters:
#                         # checking first condition
#                         # do the function
#                         cc = self.count(substr, s, maxLetters)
#                         max_count = max(max_count, cc)

#         return max_count


#     def count(self, substr, s, maxLetters):
#         # print(\"\")
#         # print(\"substr passed: \", substr)

#         # return the countOcurrences
#         count_times = 0
#         j = len(substr)

#         for i in range(len(s)-j+1):
#             # print(\"comparing with s[i:i+j]: \", s[i:i+j])
#             if s[i:i+j] == substr:
#                 count_times += 1

#         return count_times


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if len(s)<minSize:
            return 0
        if minSize>maxSize:
            return 0
        
        res=0
        d={}
        
        for i in range(len(s)-minSize+1):
            temp=s[i:i+minSize]
            if len(set(temp))<=maxLetters:
                d[temp]=d.get(temp,0)+1
                res=max(res,d[temp])
        return res
        
        '''
        res=0
        for i in range(minSize,maxSize+1):
            #print(\"a\")
            r=[]
            for j in range(i,len(s)+1):
                #print(s[j-minSize:j])
                a=s[j-minSize:j]
                
                if len(set(list(a)))<=maxLetters:
                #print(set(list(a)))
                    r.append(a)
            #print(r)
            if len(r)!=0:
                r1 = max(set(r), key = r.count) 
            #print(r.count(r1))
                r2=r.count(r1)
                res=max(res,r2)
        return res
        '''

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = collections.defaultdict(int)
        max_freq = 0
        for win in range(minSize, maxSize+1):
            for i in range(len(s) - win + 1):
                sub_seq = s[i:i+win]
                if len(set(sub_seq)) <= maxLetters:
                    freq[sub_seq] += 1
            max_freq = max(max_freq, max(freq.values()) if freq else 0)
        return max_freq

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        max_occ = 0
        
        D = {}
        for i in range(len(s)):
            for j in range(i+minSize,i+maxSize+1):
                if j <= len(s):
                    s_s = s[i:j]
                else:
                    continue
                # print(s_s)
                # print(set(s_s))

                if len(set(s_s)) <= maxLetters:
                    # print(s_s)
                    if s_s in D.keys():
                        D[s_s] +=1
                    else:
                        D[s_s] = 1
                    max_occ = max(D[s_s], max_occ)
        return max_occ

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # sliding window, subtract left, if == 0, delete from dict (sliding caterpillar)
        currDct = {}
        ansDct = defaultdict(int)
        length = len(s)
        l = 0; r = 0
        # init to min size; caterpillar sliding window
        while l + minSize < length+1:
            # expand to min
            currDct = Counter(s[l:l+minSize])
            if len(currDct) <= maxLetters:
                ansDct[s[l:l+minSize]] += 1
            else: l += 1; continue
            # expand to maxSize
            if minSize == maxSize: l += 1; continue
            r = l + minSize + 1;
            while r < length and r < l + maxSize:
                # add to the right
                currDct[s[r]] += 1
                # del to the left
                currDct[s[l]] -= 1
                if currDct[s[l]] == 0: del currDct[s[l]]
                if len(currDct) <= maxLetters:
                    ansDct[s[l:r+1]] += 1
                r += 1
            l += 1
        # print(ansDct)
        return 0 if not ansDct else max(ansDct.values())

import operator

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        freq=collections.defaultdict(int)
        
        for size in range(minSize, maxSize + 1):
            
            j = size
            window = s[0:size]
            
            while j <= len(s):
                
                if len(set(window)) <= maxLetters:
                    freq[window] += 1
                
                j += 1
                window = s[j - size:j]
                                
        if freq:
            return max(freq.values())
        else:
            return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        counter = dict()
        n = len(s)
        for i in range(n-minSize+1):
            for j in range(i+minSize-1, i+maxSize):
                if j>=n:
                    break
                if len(set(s[i:j+1]))<=maxLetters:
                    counter[s[i:j+1]] = counter.get(s[i:j+1], 0) + 1
                    
        # print(counter)
        if list(counter.values())==[]: return 0
        return max(counter.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        d = {}
        for i in range(n):
            for j in range(minSize, maxSize+1):
                if i+j> n:
                    break
                if len(set(s[i:i+j])) <= maxLetters:
                    d[ s[i:i+j] ] = d.get(s[i:i+j],0) +1
        # print(d)
        return max(list(d.values()), default=0)
                       
                       


from collections import defaultdict
from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = defaultdict(int)
        for i in range(0, len(s) - minSize + 1):
            for j in range(minSize, maxSize + 1):
                if i + j > len(s):
                    break
                cur_str = s[i:i+j]
                unique_letters = set(cur_str)
                if len(unique_letters) > maxLetters:
                    continue
                else:
                    dic[cur_str] += 1

        res = 0
        for s in dic:
            res = max(res, dic[s])
        return res

import operator

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        freq=collections.defaultdict(int)
        
        for size in range(minSize, maxSize + 1):
            
            j = size
            window = s[0:size]
            
            while j <= len(s):
                
                if len(set(window)) <= maxLetters:
                    freq[window] += 1
                
                j += 1
                window = s[j - size:j]
                                
        if freq:
            return max(freq.items(), key=operator.itemgetter(1))[1]
        else:
            return 0

from collections import Counter

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrings = {}
        for i in range(len(s)-minSize+1):
            sub = s[i:i+minSize]
            if sub in substrings:
                substrings[sub] += 1
            else:
                if len(Counter(sub)) <= maxLetters:
                    substrings[sub] = 1
        if len(substrings):
            return max(substrings.values())
        else:
            return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = 0
        ht = collections.Counter()
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                substring = s[i:j]
                length = len(substring)
                if length >= minSize and length <= maxSize and len(set(substring)) <= maxLetters:
                    ht[substring]+=1
                elif length > maxSize:
                    break
                    
        return max(v for k,v in ht.items()) if ht else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrings = dict()
        for i in range(minSize - 1, maxSize):
            for j in range(i,len(s)):
                if len(set(s[j-i: j + 1])) <= maxLetters:
                    substrings[s[j-i: j + 1]] = substrings.get(s[j-i:j + 1], 0) + 1
        return max(substrings.values()) if len(substrings) else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        seen = collections.defaultdict(int)
        n = len(s)
        for k in range(minSize,maxSize+1):
            counts = collections.Counter(s[:k])
            if len(counts) <= maxLetters:
                seen[s[:k]] += 1
            for i in range(n-k):
                counts[s[i]] -= 1
                if counts[s[i]] == 0:
                    del counts[s[i]]
                counts[s[i+k]] += 1
                if len(counts) <= maxLetters:
                    seen[s[i+1:i+k+1]] += 1
        return max(seen.values()) if len(seen) > 0 else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substrings = collections.defaultdict(int)
        for k in range(minSize,maxSize+1):
            for i in range(len(s)-k+1):
                substrings[s[i:i+k]]+=1
        maxCount = 0
        for k,v in list(substrings.items()):
            if(len(set(k))<=maxLetters):
                maxCount=max(maxCount,v)
        return maxCount


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        occurence = {}
        
        for i in range(len(s)):
            for j in range(minSize,maxSize+1):
                if i+j > len(s): 
                    break
                if len(set(s[i:i+j])) <= maxLetters:
                    if s[i:i+j] not in occurence:
                        occurence[s[i:i+j]] = 0
                    occurence[s[i:i+j]]+=1
        # print(occurence)
        if len(occurence) == 0:
            return 0
        return max(occurence.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        i=numUnique=0; N=len(s); count=collections.defaultdict(int); seen=collections.defaultdict(int)
        ans=0
        
        for i in range(N):
            count=collections.defaultdict(int)
            numUnique=0
            power=1
            hash=0
            for j in range(i,min(i+26,N)):
                count[s[j]]+=1
                if count[s[j]]==1:
                    numUnique+=1
                
                add=(ord(s[j])-ord('a')+1)*(27**power)
                hash+=add
                power+=1
                
                if numUnique>maxLetters or j-i+1>maxSize:
                    break
                
                if minSize<=j-i+1<=maxSize and numUnique<=maxLetters:
                    # have a valid subs
                    # print(s[i:j+1], hash)
                    seen[hash]+=1
                    ans=max(ans,seen[hash])
        
        return ans
                
                
                
                
        # for j in range(N):
            
        
#         for j in range(N):
#             if count[s[j]]==0:
#                 numUnique+=1
                
#             count[s[j]]+=1
            
#             while j-i+1>maxSize or numUnique>maxLetters:
#                 count[s[i]]-=1
#                 if count[s[i]]==0:
#                     numUnique-=1
#                 i+=1
                
#             if j-i+1>=minSize:
#                 # we finally have a valid substring
#                 for k in range(i,j+1):
#                     curr=\"\"
#                     for l in range(k,j+1):
#                         curr+=s[l]
#                         if len(curr)>=minSize:
#                             seen[curr]+1=26
                        
#                 subs=s[i:j+1]
#                 seen[subs]+=1
#                 ans=max(ans,seen[subs])
        
#         print(seen)
#         return ans
                
                
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if len(s) < minSize:
            return 0
        res = 0
        
        def is_good(ss):
            return len(set(ss)) <= maxLetters
        
        for sz in range(minSize, maxSize + 1):
            cnt = collections.defaultdict(int)
            
            for i in range(len(s) - sz + 1):
                if is_good(s[i:i+sz]):
                    cnt[s[i:i+sz]] += 1
                    res = max(res, cnt[s[i:i+sz]])
            #print(sz, cnt)
        return res
                
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        store = collections.defaultdict(int)
 
        for i in range(0, len(s) - minSize+ 1): 
            
            for j in range(0, maxSize-minSize + 1): 
                if (i+j+minSize) > len(s):
                    break
                subS = s[i: i+ minSize + j] 
            
                checkSize = set(subS)
                
                if len(checkSize) <= maxLetters:
                    store[subS] += 1 
        
        maxNum = 0
 
        for key, val in store.items():
            if val > maxNum:
                maxNum = val
               
        return maxNum

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        
        count = defaultdict(int)
        
        for size in range(minSize, maxSize+1):
            
            # key = [0]*26
            q = deque()
            for i in range(0, len(s)):
                
                # if i < size-1:
                # key[ord(s[i])-97] += 1
                q.append(s[i])
                

                if i > size-1:
                    q.popleft()
                
                if (i >= size-1) and len(set(q)) <= maxLetters:
                    # print(tuple(key))
                    count[tuple(q)] += 1
        
        if len(count) == 0:
            return 0
        return max(count.values())
                
                
                    
            


# O(n) time and space
# Only need minSize, if string S with size N > minSize has frequency F, then the substring of S must also have frequency F
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ans = 0
        str_freq = collections.Counter()
        
        for i in range(len(s)-minSize+1):
            candidate = s[i:i+minSize]
            
            if len(set(candidate)) <= maxLetters:
                str_freq[candidate] += 1
                ans = max(ans, str_freq[candidate])
                
        return ans

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        dic = collections.defaultdict(int)
        res = 0
        for i in range(n):
            for j in range(i+ minSize - 1,min(i+maxSize,n)):
                temp = s[i:j+1]
                if len(set(temp)) <= maxLetters:
                    dic[temp] += 1
                    res = max(res,dic[temp])
        return res

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        l = len(s)
        ans = 0
        for i in range(minSize,maxSize+1):
            mp=collections.defaultdict(int)
            for j in range(l-i+1):
                cc = collections.defaultdict(int)
                sub = s[j:j+i]
                if len(set(sub))<=maxLetters:
                    mp[sub]+=1
    
            if len(mp.keys())>0:
                ans=max(max(mp.values()),ans)
        return ans

from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = defaultdict(int)
        for size in range(minSize, maxSize+1):
            for i in range(len(s)-size+1):
                substring = s[i:i+size]
                if len(set(substring)) <= maxLetters:
                    count[substring] += 1
        if count:
            return max(count.values())      
        return 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if not s or len(s) < minSize:
            return 0
        gMax = -1
        while minSize <= maxSize:
            start = 0
            end = minSize - 1
            freqMap = {}
            lMax = 0
            while end < len(s):
                sub = s[start:end + 1]
                # print(sub, self.checkUnique(sub))
                if sub in freqMap or self.checkUnique(sub, maxLetters):
                    if sub not in freqMap:
                        freqMap[sub] = 1
                    else:
                        freqMap[sub] += 1
                    if freqMap[sub] > lMax:
                        lMax = freqMap[sub]
                start += 1
                end += 1
            # print(lMax, gMax, minSize)
            if lMax > gMax:
                gMax = lMax   
            minSize += 1
            
        return gMax
                        
                
                
    def checkUnique(self, string, maxLetters):
        sett = set(string)
        if len(sett) > maxLetters:
            return False
        else:
            return True
                
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dict = {}
        left, right = 0, minSize
        while left < len(s):
            while right - left <= maxSize and right <= len(s):
                sub = s[left:right]
                if sub in dict:
                    dict[sub] += 1
                elif self.isUniqueAmount(sub, maxLetters):
                    dict[sub] = 1

                right += 1
            
            left += 1
            right = left + minSize
        
        retValue = 0
        for k, v in list(dict.items()):
            retValue = max(retValue, v)
        
        return retValue
    
    def isUniqueAmount(self, s: str, maxLetters: int) -> bool:
        return len(set(s)) <= maxLetters 


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        onetime = False
        if minSize == maxSize:
            onetime = True
            
        valid_candidates = {}
        maxoccurrences = 0
        
        def check_candidates(test):
            nonlocal maxoccurrences
            
            if len(set(test)) <= maxLetters:
                valid_candidates[test] = valid_candidates.get(test, 0) + 1
                maxoccurrences = max(maxoccurrences, valid_candidates[test])
                
        #find all possible substrings
        for i in range(len(s)):
            for j in range(minSize, maxSize+1):
                if i + j <= len(s):
                    check_candidates(s[i:i+j])
        
        return maxoccurrences

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dict = {}
        left, right = 0, minSize
        while left < len(s):
            while right - left <= maxSize and right <= len(s):
                sub = s[left:right]
                if self.isUniqueAmount(sub, maxLetters):
                    self.addToDict(sub, dict)
                right += 1
            
            left += 1
            right = left + minSize
        
        retValue = 0
        for k, v in list(dict.items()):
            retValue = max(retValue, v)
        
        return retValue
    
    def addToDict(self, sub: str, dict: {}) -> None:
        if sub not in dict:
            dict[sub] = 0
        dict[sub] += 1
    
    def isUniqueAmount(self, s: str, maxLetters: int) -> bool:
        return len(set(s)) <= maxLetters 


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt = Counter()
        for sz in range(minSize, min(maxSize, len(s)) + 1):
            cur = Counter(s[:sz])
            if len(cur) <= maxLetters:
                cnt[s[:sz]] += 1
            for i in range(1, len(s) - sz + 1):
                # print(s[i:i+sz], s[i+sz-1])
                cur[s[i+sz-1]] += 1
                cur[s[i-1]] -= 1
                if cur[s[i-1]] == 0:
                    cur.pop(s[i-1])
                if len(cur) <= maxLetters:
                    cnt[s[i:i+sz]] += 1
        return max(cnt.values()) if cnt else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        validStrings = {}
        for currSize in range(minSize, maxSize+1):
            self.getValidString(currSize, s, maxLetters, validStrings)
        return self.getMaxCount(validStrings)
        
    def getValidString(self,currSize, s, maxLetters, validStrings):
        left = 0
        right = 0
        currWindow = {}
        uniqueCounts = 0
        for right in range(currSize):
            uniqueCounts = self.insert(s[right],currWindow, uniqueCounts)
        self.insertValidString(uniqueCounts,maxLetters, left, right, s, validStrings )
        while right < len(s)-1:
            uniqueCounts = self.insert(s[right+1],currWindow, uniqueCounts)
            uniqueCounts = self.remove(s[left],currWindow, uniqueCounts)
            left += 1
            right += 1
            self.insertValidString(uniqueCounts,maxLetters, left, right, s, validStrings )
            
    def insert(self,char,currWindow, uniqueCounts):
        if char not in currWindow:
            currWindow[char] = 1
            uniqueCounts += 1
        else:
            currWindow[char] += 1
        return uniqueCounts
    
    def remove(self,char,currWindow, uniqueCounts):
        currWindow[char] -= 1
        if currWindow[char] == 0:
            del currWindow[char]
            uniqueCounts -= 1
        return uniqueCounts
    
    def getMaxCount(self,validStrings):
        maxCount = 0
        for string in validStrings:
            if validStrings[string] > maxCount:
                maxCount = validStrings[string]
        return maxCount
    
    
    def insertValidString(self,uniqueCounts,maxLetters, left, right, s, validStrings ):
        if uniqueCounts <= maxLetters:
            currWord = s[left:right+1]
            if currWord not in validStrings:
                validStrings[currWord] = 1
            else:
                validStrings[currWord] += 1

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        substr = collections.Counter()
        counter = [collections.Counter(s[:minSize])]
        if len(counter[-1]) <= maxLetters:
            substr[s[:minSize]] += 1
        for i in range(1, maxSize - minSize + 1):
            counter.append(collections.Counter(counter[-1]))
            counter[-1][s[minSize + i - 1]] += 1
            if len(counter[-1]) <= maxLetters:
                substr[s[:minSize + i]] += 1
        # print(counter)
        # print(substr)
        for i in range(minSize, n):
            l = i - minSize
            for j, cnt in enumerate(counter):
                r = i + j
                if r >= n:
                    break
                cnt[s[l]] -= 1
                cnt[s[r]] += 1
                if cnt[s[l]] == 0:
                    cnt.pop(s[l])
                if len(cnt) <= maxLetters:
                    substr[s[l + 1: r + 1]] += 1
        #     print(counter)
        # print(substr)
        return max(substr.values(), default=0)

class Solution:        
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if len(s) == len(set(s)):
            return 0
        from collections import defaultdict
        corpus = defaultdict(int)
        
        for i in range(minSize, maxSize+1):
            for j in range(len(s) - i + 1):
                if len(set(s[j:j+i])) <= maxLetters:
                    corpus[s[j:j+i]] += 1
        
        if len(corpus) == 0:
            return 0
        
        return max(corpus.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        count = 0
        diff = maxSize-minSize
        hashM = {}
        maxC = float('-inf')
        
        for r in range(len(s)-minSize+1):
            
            for i in range(diff+1):
                
                if r + minSize + i <= len(s):
                    if len(set(s[r:r+minSize+i])) <= maxLetters:

                        hashM[s[r:r+minSize+i]] = hashM.get(s[r:r+minSize+i], 0) + 1
                        maxC = max(maxC, hashM[s[r:r+minSize+i]])
                        
        return(maxC if maxC != float('-inf') else 0)


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
                
        counts = {} # string -> number 
        
        for current_size in range(minSize, maxSize + 1): 
            window = {}
            for i in range(current_size): 
                c = s[i]
                window[c] = window.get(c, 0) + 1 

            for i in range(current_size, len(s) + 1):
                start = i - current_size
                if len(window) <= maxLetters: 
                    sub = s[start:i]
                    counts[sub] = counts.get(sub, 0) + 1 
                if i == len(s): 
                    break
                    
                # add current 
                c = s[i]
                window[c] = window.get(c, 0) + 1 
                # remove tail
                c = s[start]
                window[c] -= 1 
                if window[c] == 0:
                    del window[c]

        # print(counts)
        return max(counts.values()) if len(counts) else 0 


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        lookup = {}
        
        for size in range(minSize, maxSize + 1):
            for i in range(0, len(s) - size + 1):
                sub_s = s[i:i+size]
                if len(set(sub_s)) <= maxLetters:
                    if sub_s not in lookup:
                        lookup[sub_s] = 0
                    lookup[sub_s] += 1
                
        if not lookup:
            return 0

        return max(lookup.values()) 

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
       
        start = 0
        end = 0
        sub = {}
        result = {}
        self.max_size = 0
        
        def add_sub(pos):
            if s[pos] in sub:
                sub[s[pos]] +=1
            else:
                sub[s[pos]] = 1
        
        def rem_sub(pos):
            if s[pos] in sub:
                if sub[s[pos]] == 1:
                    del sub[s[pos]]
                else:
                    sub[s[pos]] -= 1
        def add_res(string):
            if string in result:
                result[string] +=1
            else:
                result[string] = 1
            self.max_size = max(self.max_size,result[string])
        
        for size in range(minSize,maxSize+1):
            while start <= len(s)-size:
                if (end-start)+1 < size:
                    add_sub(end)
                    end +=1
                else:
                    add_sub(end)
                    if len(sub) <= maxLetters:
                        add_res(s[start:end+1])
                    rem_sub(start)
                    start +=1
                    end +=1
            start = 0
            end = 0
            sub = {}
            
        return self.max_size
        
        
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        my_dict = {}
        for i in range(len(s)-minSize+1):
            if len(set(s[i:i+minSize]))<=maxLetters:
                if s[i:i+minSize] in my_dict:
                    my_dict[s[i:i+minSize]] += 1
                else:
                    my_dict[s[i:i+minSize]] = 1
        # print(my_dict)
        k = minSize+1
        if minSize!=maxSize:
            while(maxSize>=k):
                for i in range(len(s)-k+1):
                    if len(set(s[i:i+k]))<=maxLetters:
                        if s[i:i+k] in my_dict:
                            my_dict[s[i:i+k]] += 1
                        else:
                            my_dict[s[i:i+k]] = 1
                # print(my_dict)
                k+=1
        return max(my_dict.values()) if my_dict else 0
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = Counter()
        for k in range(minSize, maxSize + 1):
            window = Counter(s[:k])
            if len(window) <= maxLetters:
                count[s[:k]] += 1
            for i in range(k, len(s)):
                window[s[i]] += 1
                window[s[i - k]] -= 1
                if window[s[i - k]] == 0:
                    del window[s[i - k]]
                if len(window) <= maxLetters:
                    count[s[i - k + 1:i + 1]] += 1
        return max(list(count.values()), default=0)


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        wordCounter = collections.defaultdict()
        
        # loop (maxSize - minSize)+1 times
        for i in range((maxSize - minSize)+1):
            charCounter = collections.Counter(s[:minSize+i])
            if len(charCounter) <= maxLetters:
                    wordCounter[s[:minSize+i]] = 1
           
            for j in range(minSize+i, len(s)):
                charCounter[s[j-minSize-i]] -= 1
                
                if charCounter[s[j-minSize-i]] <= 0:
                    del charCounter[s[j-minSize-i]]
    
                charCounter[s[j]] += 1
                if len(charCounter) <= maxLetters:
                    if s[j-minSize-i+1:j+1] in wordCounter:
                        wordCounter[s[j-minSize-i+1:j+1]] += 1
                    else:
                        wordCounter[s[j-minSize-i+1:j+1]] = 1
      
        maxTimes = 0
        for subString in wordCounter:
            maxTimes = max(wordCounter[subString], maxTimes)
        return maxTimes

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        res_dict = collections.defaultdict(int)
        
        for lidx in range(n-minSize+1):
            lval = lidx+minSize
            rval = min(n,lidx+maxSize+1)
            for ridx in range(lval, 1+rval):
                counts = collections.Counter(s[lidx:ridx])
                if len(counts) <= maxLetters:
                    res_dict[s[lidx:ridx]] += 1
                else: 
                    break
        
        return max(res_dict.values()) if res_dict else 0

import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        # for each substring of length, find unique chars
        maxC = Counter()
        ans = 0
        for sz in range(minSize, maxSize+1):
            unq = Counter()
            for i in range(sz):
                unq[s[i]] += 1
                
            if (len(unq) <= maxLetters): 
                maxC[s[0:sz]] += 1
                if(maxC[s[0:sz]] > ans): ans=maxC[s[0:sz]]
            
            i, j = 0, sz - 1
            while (j < len(s) - 1):
                unq[s[i]] -= 1
                if (unq[s[i]] == 0): del unq[s[i]]
                
                i+=1
                j+=1
                
                unq[s[j]] += 1
                
                if (len(unq) <= maxLetters): 
                    maxC[s[i:j+1]] += 1
                    if(maxC[s[i:j+1]] > ans): ans=maxC[s[i:j+1]]

        return ans

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        subset_d = {}

        for i in range(minSize, maxSize + 1):
            for j in range(0, len(s) - i + 1):
                substr = s[j:j + i]
                subset_d[substr] = subset_d.get(substr, 0) + 1
                
        max_occur = 0
        for substr, val in list(subset_d.items()):
            temp_s = set(list(substr))
            
            if val > max_occur and len(temp_s) <= maxLetters:
                max_occur = val
                
        return max_occur


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        lenS = len(s)
        
        #for counting uniq chars :
        uniqSubStrDict = {}   
        
        #for i,char in enumerate(s):
        #    uniqDict[char] = i                         
        count = 0
        # edge casses:
    
        # main alg.
        Max = 0;
        for i in range(minSize,maxSize + 1):
            for j in range(lenS - i + 1) : # maxSize):
                
                tstSubStr = s[j : j + i]
                uniqChars = {}
                for k in tstSubStr:
                    uniqChars[k] = 1 #uniqChars.get(k,0) + 1
                    
                if len(uniqChars) > maxLetters:
                    #print(' in over maxLetters loop -- tstSubStr = {} '.format(tstSubStr))
                    continue
                    
                #print(' tstSubStr = {} '.format(tstSubStr))
                uniqSubStrDict[tstSubStr] = uniqSubStrDict.get(tstSubStr,0) + 1
                #print(' dict count = {} '.format(uniqSubStrDict[tstSubStr]))
                
                if uniqSubStrDict[tstSubStr] > Max :
                    Max = uniqSubStrDict[tstSubStr]
                    
        count = Max
        #count = uniqSubStrDict[tstSubStr]
                
        return count

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dict = {}
        left, right = 0, minSize
        while left < len(s):
            while right - left <= maxSize and right <= len(s):
                sub = s[left:right]
                if self.isSize(sub, minSize, maxSize) and self.isUniqueAmount(sub, maxLetters):
                    self.addToDict(sub, dict)
                right += 1
            
            left += 1
            right = left + minSize
        
        retValue = 0
        for k, v in list(dict.items()):
            retValue = max(retValue, v)
        
        return retValue
    
    def addToDict(self, sub: str, dict: {}) -> None:
        if sub not in dict:
            dict[sub] = 0
        dict[sub] += 1
    
    def isSize(self, s: str, minSize: int, maxSize: int) -> bool:
        length = len(s)
        return minSize <= length and maxSize >= length
    
    def isUniqueAmount(self, s: str, maxLetters: int) -> bool:
        return len(set(s)) <= maxLetters 


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        newDict = {}
        
        for j in range(len(s) - minSize + 1):
            word = s[j:j+minSize]
            
            if word in newDict:
                newDict[word] += 1
                
            else:
                if len(collections.Counter(word)) <= maxLetters:
                    newDict[word] = 1
                    
        return max(newDict.values()) if len(newDict) != 0 else 0
        


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = {}
        for i in range(0, len(s)-minSize+1):
            sub = s[i:i+minSize]
            chars = set()
            for c in sub:
                chars.add(c)
            if len(chars)<=maxLetters:
                if sub not in freq: freq[sub] = 0
                freq[sub] += 1
        best = 0
        for sub in freq:
            if freq[sub] > best:
                best = freq[sub]
        return best

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        #close the window, + 1
        
        
        hashmap = {}
        occ = {}
        for i in range(len(s)):
            hashmap[s[i]] = hashmap.get(s[i], 0) + 1
            
            
            if i>=minSize:
                #remove the first
                hashmap[s[i-minSize]] -=1
                if hashmap[s[i-minSize]] == 0:
                    del hashmap[s[i-minSize]]
            if i >= minSize -1:
                if len(hashmap) <= maxLetters:
                    substring = s[i-minSize+1: i+1]
                    occ[substring] = occ.get(substring, 0) + 1 
        
        if len(occ) == 0:
            return 0
        return max(occ.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        candidates = collections.Counter()
        
        for i in range(len(s)-minSize+1):
            if len(set(list(s[i:i+minSize])))<=maxLetters:
                candidates[s[i:i+minSize]] += 1
        
        return max(list(candidates.values())+[0])


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = collections.Counter(s[i:i+minSize] for i in range(len(s)-minSize+1))
        return max([count[w] for w in count if len(set(w)) <= maxLetters] +[0])

class Solution:
  def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    counter = collections.defaultdict(int)
    mapping = collections.defaultdict(int)
    if len(s) < minSize:
      return 0
    count = 0
    for i in range(minSize):
      mapping[s[i]] += 1
      if mapping[s[i]] == 1:
        count += 1
    if count <= maxLetters:
      counter[s[0:minSize]] += 1
    for i in range(1, len(s) - minSize+1):
      mapping[s[i-1]] -= 1
      if mapping[s[i-1]] == 0:
        count -= 1
      mapping[s[i+minSize-1]] += 1
      if mapping[s[i+minSize-1]] == 1:
        count += 1
      # print(s[i:i+minSize])
      if count <= maxLetters:
        counter[s[i:i+minSize]] += 1
    # print(counter)
    if not counter:
      return 0
    return max(counter.values())
        
        


class Solution:
    def maxFreq(self, s, maxLetters, minSize, maxSize):
        
        result = 0
        subStringFreq = collections.defaultdict(int)
        window = collections.defaultdict(int)
        
        low = 0
        high = 0

        while high < len(s):
            window[s[high]] += 1   
            if (high - low + 1) == minSize:
                if len(window) <= maxLetters:  
                    subStringFreq[s[low:high+1]] += 1
                    result = max(result, subStringFreq[s[low:high+1]]) 
                    
                window[s[low]] -= 1
                if window[s[low]] == 0:
                    del window[s[low]]

                low += 1
            high += 1 
        return result

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        x=defaultdict(int)
        for i in range(len(s)-minSize+1):
            sub=s[i:i+minSize]
            if len(set(sub))<=maxLetters:
                x[sub]+=1
        return max(x.values(),default=0)

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        left = 0
        result = 0
        count = collections.defaultdict(int)
        occurances = collections.defaultdict(int)
        
        for right, char in enumerate(s):
            count[char] += 1
            while(right - left + 1 > minSize):
                count[s[left]] -= 1
                if count[s[left]] == 0:
                    del count[s[left]]
                left += 1
                
            if right - left + 1 == minSize and len(count) <= maxLetters:
                occurances[s[left:right+1]] += 1
                result = max(result, occurances[s[left:right+1]])
        return result

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = collections.defaultdict(int)
        
        for i in range(len(s) - minSize + 1):
            freq[s[i:i + minSize]] += 1
        
        mx = 0

        for key in freq:
            if len(set(key)) <= maxLetters and mx < freq[key]:
                mx = freq[key]
            
        return mx

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        l = 0
        r = 0
        strMap = collections.defaultdict(int)
        curr = ''
        currMap = collections.defaultdict(int)
        while r < len(s):
            char = s[r]
            currMap[char] += 1
            curr += char
            while len(currMap) > maxLetters or len(curr) > minSize:
                curr = curr[1:]
                currMap[s[l]] -= 1
                if currMap[s[l]] == 0:
                    del currMap[s[l]]
                l += 1
            if len(curr) == minSize:
                strMap[curr] += 1
            r += 1
        return max(strMap.values()) if strMap else 0


from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        subCt = defaultdict(int)
        currS = defaultdict(int)
        mx = 0
        l = 0
        r = 0
        
       
        while l < len(s) - minSize:
            length = r - l + 1
           
            if length > minSize:
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
                
#             c = (r == len(s) - 1) and (l < len(s) - minSize)
           
#             if c:
#                 currS[s[l]] -= 1
#                 if currS[s[l]] <= 0:
#                     del currS[s[l]]
                    
#                 l += 1
            
            currC = s[r]
            currS[currC] += 1
            
            condition =  (r - l + 1) >= minSize and len(list(currS.keys())) <= maxLetters
            if condition:
                sub = s[l:r+1]
                subCt[sub] += 1
                
                if subCt[sub] > mx:
                    mx = subCt[sub]
            
            if r < len(s) - 1:
                r += 1
            
        return mx
            


from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        subCt = defaultdict(int)
        currS = defaultdict(int)
        mx = 0
        l = 0
        r = 0
        
       
        while l < len(s) - minSize:
            length = r - l + 1
           
            if length > minSize:
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
            
            currC = s[r]
            currS[currC] += 1
            
            condition =  (r - l + 1) >= minSize and len(list(currS.keys())) <= maxLetters
            if condition:
                sub = s[l:r+1]
                subCt[sub] += 1
                
                if subCt[sub] > mx:
                    mx = subCt[sub]
            
            if r < len(s) - 1:
                r += 1
            
        return mx
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if not s:
            return 0
        
        n = len(s)
        substring_count = defaultdict(int)
        
        memo_char = defaultdict(int)
        reader = 0
        writer = 0
        
        while reader < len(s):
            ch = s[reader]
            memo_char[ch] += 1
            window_len = reader - writer +1
            
            while len(memo_char) > maxLetters or window_len > minSize:
                wch = s[writer]
                memo_char[wch] -= 1
                
                if memo_char[wch] == 0:
                    del memo_char[wch]
                
                writer += 1
                window_len = reader - writer +1
            if window_len >= minSize and window_len <= maxSize:
                substring_count[tuple(s[writer:reader+1])] += 1
                #print (s[writer:reader+1], substring_count, window_len)
            reader += 1
            
        if not substring_count:
            return 0
        
        return max(substring_count.values())
        
        


from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        subCt = defaultdict(int)
        currS = defaultdict(int)
        mx = 0
        l = 0
        r = 0
        
       
        while l < len(s) - minSize:
            length = r - l + 1
           
            if length > minSize:
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
                
            c = (r == len(s) - 1) and (l < len(s) - minSize)
           
            if c:
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
            
            currC = s[r]
            currS[currC] += 1
            
            condition =  (r - l + 1) >= minSize and len(list(currS.keys())) <= maxLetters
            if condition:
                sub = s[l:r+1]
                subCt[sub] += 1
                
                if subCt[sub] > mx:
                    mx = subCt[sub]
            
            if r < len(s) - 1:
                r += 1
            
        return mx
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        l = 0
        r = 0
        strMap = collections.defaultdict(int)
        curr = ''
        currMap = collections.defaultdict(int)
        unique = 0
        while r < len(s):
            char = s[r]
            if currMap[char] == 0:
                unique += 1
            currMap[char] += 1
            curr += char
            while unique > maxLetters or len(curr) > minSize:
                curr = curr[1:]
                currMap[s[l]] -= 1
                if currMap[s[l]] == 0:
                    unique -= 1
                l += 1
            print(curr)
            if len(curr) >= minSize:
                strMap[curr] += 1
            r += 1
        return max(list(strMap.values()) or (0,0))


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = {}
        for i in range(len(s)-minSize+1):
            s1 = s[i:i+minSize]
            unique = {}
            for c in s1:
                if c not in unique:
                    unique[c] = 1
            if len(unique) <= maxLetters:
                if s1 in dic:
                    dic[s1] += 1
                else:
                    dic[s1] = 1
                if i != len(s)-minSize and minSize != maxSize:
                    s2 = s[i:i+maxSize]
                    if s2[-1] not in unique:
                        unique[s2[-1]] = 1
                    if len(unique) <= maxLetters:
                        if s2 in dic:
                            dic[s2] += 1
                        else:
                            dic[s2] = 1
        max_occr = 0
        for key in dic:
            if dic[key] > max_occr:
                max_occr = dic[key]
        return max_occr

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # actually don't need to go up to maxSize since if
        # a string of maxSize has an occurence, then any substring
        # has at least an equal number of occurences

        seen = collections.defaultdict(int)
        n = len(s)
        counts = collections.Counter(s[:minSize])
        if len(counts) <= maxLetters:
            seen[s[:minSize]] += 1
        for i in range(n-minSize):
            counts[s[i]] -= 1
            if counts[s[i]] == 0:
                del counts[s[i]]
            counts[s[i+minSize]] += 1
            if len(counts) <= maxLetters:
                seen[s[i+1:i+minSize+1]] += 1
        return max(seen.values()) if len(seen) > 0 else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        strcount = Counter()
        unique = set(s[:minSize])
        front = 0
        back = minSize

        while back < len(s):
            if len(unique) <= maxLetters:
                strcount[s[front:back]] = strcount.get(s[front:back], 0) + 1
            front+=1
            back+=1
            unique = set(s[front:back])
        if len(unique) <= maxLetters:
            strcount[s[front : back]] = strcount.get(s[front : back], 0) + 1

        return max(list(strcount.values()) or [0])


from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = defaultdict(int)
        d = defaultdict(int)
        max_freq = 0
        for idx, a in enumerate(s):
            count[a] += 1
            if idx > minSize - 1:
                last = s[idx - minSize]
                count[last] -= 1
                if count[last] == 0:
                    del count[last]
            
            if idx >= minSize - 1:
                if len(count) <= maxLetters:
                    d[s[idx-minSize+1: idx+1]] += 1
                    max_freq = max(max_freq, d[s[idx-minSize+1: idx+1]])
        
        return max_freq
                
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = 0
        left = 0
        right = minSize-1
        d = {}
        length = len(s)
        unique_let = {}
        def popLetter(letter, n):
            unique_let[letter] -= 1
            if unique_let[letter] == 0:
                n -= 1
            return n
        def addLetter(letter, n):
            if unique_let.get(letter, 0) == 0:
                n += 1
            unique_let[letter] = unique_let.get(letter,0) + 1
            return n
        for letter in s[:minSize-1]:
            n = addLetter(letter, n)
        print(n)
        print(unique_let)
        while right < length:
            if left > 0:
                n = popLetter(s[left-1], n)
            n = addLetter(s[right], n)
            print(n)
            if n <= maxLetters:
                d[s[left:right+1]] = d.get(s[left:right+1], 0) + 1
            right += 1
            left += 1
        print(d)
        if not d.values():
            return 0
        return max(d.values())

import operator
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        lp = 0
        rp = lp + minSize
        perm_dict= {}
        for i in range(len(s)-minSize+1):
            temp = s[lp:rp]
            if len(set(temp))<=maxLetters:
                if temp not in list(perm_dict.keys()):
                    perm_dict[temp]=1
                else:
                    perm_dict[temp]+=1
            i+=1
            lp+=1
            rp+=1
        print(perm_dict)
        perm_dict = dict(sorted(list(perm_dict.items()), key=operator.itemgetter(1),reverse=True))
        if len(list(perm_dict.keys()))>0:
            return perm_dict[list(perm_dict.keys())[0]]
        return 0
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n = len(s)
        s0 = s[:minSize]
        counter = collections.Counter(s0)
        substr = collections.Counter()
        if len(counter) <= maxLetters:
            substr[s0] += 1
        for i in range(minSize, n):
            l = i - minSize
            counter[s[i - minSize]] -= 1
            counter[s[i]] += 1
            if counter[s[i - minSize]] == 0:
                counter.pop(s[i - minSize])
            if len(counter) <= maxLetters:
                substr[s[i - minSize + 1: i + 1]] += 1
        return max(substr.values(), default=0)

class Solution:
    def maxFreq(self, S, maxchars, minsize, maxsize):
        n=len(S)
        freq=Counter()
        chars=Counter()
        i=0
        for j in range(n):
            if j-i+1>minsize:
                chars[S[i]]-=1
                if chars[S[i]]==0:
                    del chars[S[i]]
                i+=1
            chars[S[j]]+=1
            if j-i+1>=minsize:
                if len(chars)<=maxchars:
                    freq[S[i:j+1]]+=1
        return max(freq.values(),default=0)

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        i=0
        j=0
        map1={}
        res={}
        while j<len(s):
            map1[s[j]]=map1.get(s[j],0)+1
            if len(map1.keys())>maxLetters:
                map1[s[i]]=map1[s[i]]-1
                if map1[s[i]]==0:
                    del map1[s[i]]
                i+=1
            while len(map1.keys())<=maxLetters and j-i+1<=maxSize and j-i+1>=minSize:
                #add to result first
                res[s[i:j+1]]=res.get(s[i:j+1],0)+1
                
                #remove the existing s[i]'s value from map
                
                map1[s[i]]=map1[s[i]]-1
                if map1[s[i]]==0:
                    del map1[s[i]]
                
                #move i=i+1
                i=i+1
            j=j+1
        if len(res)==0:
            return 0
        else:
            maximum = max(res, key=res.get)
            return res[maximum]

from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        subCt = defaultdict(int)
        currS = defaultdict(int)
        mx = 0
        l = 0
        r = 0
        
       
        while l < len(s) - minSize:
            length = r - l + 1
           
            if length > minSize:
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
                
            c = (r == len(s) - 1) and (l < len(s) - minSize)
           
            if c:
                print('eer')
                currS[s[l]] -= 1
                if currS[s[l]] <= 0:
                    del currS[s[l]]
                    
                l += 1
            
            currC = s[r]
            currS[currC] += 1
            
            condition =  (r - l + 1) >= minSize and len(list(currS.keys())) <= maxLetters
            if condition:
                sub = s[l:r+1]
                print(sub)
                subCt[sub] += 1
                
                if subCt[sub] > mx:
                    mx = subCt[sub]
            
            if r < len(s) - 1:
                r += 1
            
        return mx
            


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if len(s) == 0:
            return 0
        rolling_hash = 0
        letter_counts = collections.Counter()
        hash_counts = collections.Counter()
        unique_letters = set()
        n = len(s)
        
        for i in range(n):
            ch = s[i]
            
            rolling_hash = rolling_hash * 26 + ord(ch)
            letter_counts[ch] += 1
            unique_letters.add(ch)
            
            if i + 1 < minSize:
                continue
            
            if len(unique_letters) <= maxLetters:
                hash_counts[rolling_hash] += 1
                
            remove_letter = s[i - minSize + 1]
            rolling_hash -= (ord(remove_letter)) * 26**(minSize-1)
            letter_counts[remove_letter] -= 1
            
            if letter_counts[remove_letter] == 0:
                unique_letters.remove(remove_letter)
        return max(hash_counts.values()) if len(hash_counts) else 0 

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:

        count = collections.Counter(s[i:i + minSize] for i in range(len(s) - minSize + 1))
        return max([count[w] for w in count if len(set(w)) <= maxLetters] + [0])


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        window_start = 0
        window_letters = Counter()
        
        substring_counts = Counter()
        
        for window_end in range(len(s)):
            window_letters[s[window_end]] += 1
            substring_len = window_end-window_start+1
            
            while substring_len > maxSize or len(window_letters) > maxLetters:
                start_char = s[window_start]
                window_letters[start_char] -= 1
                if window_letters[start_char] == 0:
                    del window_letters[start_char]
                window_start += 1
                substring_len = window_end-window_start+1
            
            while substring_len >= minSize:
                assert substring_len <= maxSize
                substring = s[window_start:window_end+1]
                substring_counts[substring] += 1
                
                start_char = s[window_start]
                window_letters[start_char] -= 1
                if window_letters[start_char] == 0:
                    del window_letters[start_char]
                window_start += 1
                substring_len = window_end-window_start+1
        print(substring_counts)
        if not substring_counts:
            return 0
        return max(substring_counts.values())
            
            
                


import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        # for each substring of length, find unique chars
        maxC = Counter()
        ans = 0
        sz = minSize
        unq = Counter()
        for i in range(sz):
            unq[s[i]] += 1

        if (len(unq) <= maxLetters): 
            maxC[s[0:sz]] += 1
            if(maxC[s[0:sz]] > ans): ans=maxC[s[0:sz]]

        i, j = 0, sz - 1
        while (j < len(s) - 1):
            unq[s[i]] -= 1
            if (unq[s[i]] == 0): del unq[s[i]]

            i+=1
            j+=1

            unq[s[j]] += 1

            if (len(unq) <= maxLetters): 
                maxC[s[i:j+1]] += 1
                if(maxC[s[i:j+1]] > ans): ans=maxC[s[i:j+1]]

        return ans

class Solution:
    def maxFreq(self, s: str, maxy: int, m: int, mm: int) -> int:
        
        i,j = 0,0
        count = collections.Counter()
        count[s[0]]+=1
        ans = collections.Counter()
        u, n = 1, len(s)
        
        key = s[0]
        
        while True:
            if u<=maxy and m<=i-j+1<=mm: 
                ans[key]+=1
            
            if j<i and i-j+1>=m:
                count[s[j]]-=1
                if count[s[j]]==0: u-=1
                j+=1
                key = key[1:]
            else:
                i+=1
                if i == n: break
                if count[s[i]]==0: u+=1
                count[s[i]]+=1
                key+=s[i]
            
        return max(ans.values()) if ans else 0

class Solution:
    def maxFreq(self, s: str, maxy: int, m: int, mm: int) -> int:
        
        i,j = 0,0
        count = collections.Counter()
        count[s[0]]+=1
        ans = collections.Counter()
        u = 1
        n = len(s)
        while True:
            # print(f'j-{j}, i-{i}, u-{u}, ans-{ans}')
            if u<=maxy and m<=i-j+1<=mm: 
                # print('Found!-',j,i,s[j:i+1])
                ans[s[j:i+1]]+=1
            
            if j<i and i-j+1>=m:
                count[s[j]]-=1
                if count[s[j]]==0: u-=1
                j+=1
            else:
                i+=1
                if i == n: break
                if count[s[i]]==0: u+=1
                count[s[i]]+=1
        print(ans)
        return max(ans.values()) if ans else 0

from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if not s or len(s) < minSize: return 0
        res = defaultdict(int)
        res[''] = 0
        temp = defaultdict(int)
    
        i = 0
        j = minSize-1

        for k in range(minSize):
            temp[s[k]] += 1
        
        if len(temp.keys()) <= maxLetters:
                res[s[i:j+1]] += 1
            
        while i < len(s)-minSize:
            temp[s[i]] -= 1
            i += 1
            j += 1
            temp[s[j]] += 1
            if len([l for l in temp if temp[l]]) <= maxLetters:
                res[s[i:j+1]] += 1
        
        return max(res.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        from collections import defaultdict, Counter
        d = defaultdict(int)
        for i in range(len(s)-minSize+1):
            t = s[i:i+minSize]
            if len(Counter(t)) <= maxLetters:
                d[t] += 1
        return max(d.values()) if d else 0


from collections import Counter, defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        d = defaultdict(int)
        for i in range(len(s)-minSize+1):
            sub = s[i:i+minSize]
            if len(Counter(sub)) <= maxLetters:
                d[sub] += 1
        return max(d.values()) if len(list(d.values())) else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = {}
        for i in range(len(s) - minSize + 1):
            word = s[i: i+minSize]
            if word in count:
                count[word] += 1
            else:
                if len(set(word)) <= maxLetters:
                    count[word] = 1
        return max(count.values()) if count else 0

from collections import Counter

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        i = 0
        j = 0
        letterCounts = Counter()
        substrCounts = Counter()
        
        while j < len(s):
            letterCounts[s[j]] += 1

            while len(letterCounts) > maxLetters or j - i + 1 > minSize:
                letterCounts[s[i]] -= 1
                if letterCounts[s[i]] == 0:
                    del letterCounts[s[i]]
                i += 1
            
            if j - i + 1 == minSize:
                substrCounts[s[i:j + 1]] += 1
            
            j += 1
        
        return 0 if len(substrCounts) == 0 else max(substrCounts.values())

'''
uniq<=max
len(sub)>=min and <=max
'''
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        hash,w_hash,res={},{},float('-inf')
        self.initial_fill(s,minSize,hash)
        for i in range(0,len(s)-minSize+1):
            if len(hash)<=maxLetters:
                string=s[i:i+minSize]
                w_hash[string]=1 if string not in w_hash else w_hash[string]+1
                res=max(res,w_hash[string])
            char=s[i]
            if hash[char]==1: del hash[char]
            else: hash[char]-=1
            if i+minSize<len(s):
                char=s[i+minSize]
                hash[char]=1 if char not in hash else hash[char]+1
        return res if res!=float('-inf') else 0
                
            
    
    def initial_fill(self,s,Min,hash):
        for i in range(0,Min):
            char=s[i]
            hash[char]=1 if char not in hash else hash[char]+1

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        left=0
        right=0
        _dict=defaultdict(int)
        _dict2=defaultdict(int)
     
        while right<len(s):
            _dict[s[right]]+=1
           
        
            while len(_dict)>maxLetters or right-left+1>maxSize or right-left+1>minSize:
                _dict[s[left]]-=1
                if _dict[s[left]]==0:
                    del(_dict[s[left]])
                left+=1
            if  len(_dict)<=maxLetters and minSize<=right-left+1<=maxSize :
                    _dict2[s[left:right+1]]+=1                      
                
            right+=1
          
        if len(_dict2)==0:
            return 0
      
        return max(_dict2.values())
        
                


import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        dic = collections.defaultdict(int)
        for i in range(len(s) - minSize + 1):
            if len(collections.Counter(s[i:i + minSize])) <= maxLetters:
                dic[s[i:i + minSize]] += 1
        if not dic:
            return 0
        return max(dic.values())


from collections import defaultdict, Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        def hasUnique(s):
            dic = Counter(s)
            if(len(dic) <= maxLetters):
                return True
            return False
        
        def checkSubStrings(s):
            dic = defaultdict(int)
            maximum = 0
            for i in range(0, len(s) - minSize + 1):
                end = i + minSize
                strr = s[i:end]
                if(hasUnique(strr)):
                    dic[strr] += 1
                    maximum = max(maximum,  dic[strr])
                        
            return maximum
                    
        return(checkSubStrings(s))

from collections import defaultdict
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        cnt = defaultdict(int)
        freq = defaultdict(int)
        res, left = 0, 0
        for i in range(len(s)):
            cnt[s[i]] = cnt.get(s[i], 0) + 1
            while len(cnt) > maxLetters or i - left + 1 > minSize:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    del cnt[s[left]]
                left += 1
            if (i - left + 1 <= maxSize and i - left + 1 >= minSize):
                sub = s[left: i + 1]
                freq[sub] = freq.get(sub, 0) + 1
        return max(freq.values()) if freq else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        memo_dict = {}
        for i in range(len(s)):
            for j in range(i,len(s) + 1):
                if j - i < minSize:
                    continue
                if j - i > minSize:
                    break
                temp = []
                temp_str = s[i:j]
                for char in temp_str:
                    temp.append(char)
                if len(set(temp)) > maxLetters:
                    continue
                
                if temp_str in memo_dict:
                    memo_dict[temp_str] += 1
                else:
                    memo_dict[temp_str] = 1
                    
        if len(memo_dict) == 0: return 0            
        res = sorted(memo_dict, key = lambda x : memo_dict[x])
        #print(res)    
        return memo_dict[res[-1]]
                    
                    


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        counterSubstring = collections.defaultdict(int)
        best = 0
        for start in range(len(s)):
            #for size in range(minSize, maxSize + 1):
            if start + minSize <= len(s):
                substring = s[start:start + minSize]
                counterSubstring[substring] += 1
        
        for substring in counterSubstring:
            if len(set(substring)) <= maxLetters:
                best = max(best, counterSubstring[substring])
        
        return best      

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq = Counter()
        for leftInd, char in enumerate(s):
            seen = set([])
            for rightInd in range(leftInd, leftInd + minSize):
                if rightInd > len(s) - 1:
                    break
                seen.add(s[rightInd])
                if len(seen) > maxLetters:
                    break
                if rightInd - leftInd + 1 >= minSize:
                    freq[s[leftInd:rightInd + 1]] += 1
        ret = 0
        for key, val in freq.items():
            ret = max(ret, val)
        return ret

import collections
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        max_occur = 0
        freq_hash = {}
        for i in range(len(s) - minSize + 1):
            stri = s[i: i + minSize]
            if len(collections.Counter(stri)) <= maxLetters:
                if stri in freq_hash:
                    freq_hash[stri] += 1
                else:
                    freq_hash[stri] = 1
                max_occur = max(max_occur, freq_hash[stri])
        return max_occur
        # counts = dict()
        # for j in range(len(s)-minSize+1):
        #     word = s[j:j+minSize]
        #     if word in counts:
        #         counts[word]+=1
        #     else:
        #         if len(collections.Counter(word))<=maxLetters:
        #             counts[word]=1
        # return max(counts.values()) if len(counts)!=0 else 0


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        ans = 0
        l = minSize
        counts = {}
        for i in range(len(s) - l + 1):
            string = s[i:i+l]
            c = collections.Counter(string)
            if len(c) <= maxLetters:
                counts[string] = counts.get(string, 0) + 1

        if counts:
            ans = max(ans, max(counts.values()))
        
        return ans

from collections import Counter

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        if len(s) < minSize or maxSize == 0:
            return 0
        
        start = 0
        end = start + minSize
        count = Counter()
        
        while end <= len(s):
            unique = Counter(s[start:end])
            
            if len(unique) <= maxLetters:
                count[s[start:end]] += 1
            start += 1
            end += 1
        return max(count.values()) if count else 0

from collections import Counter
from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # init first window
        counts = defaultdict(int)
        substrs = defaultdict(int)
        start = 0
        # expand window until we can't any more 
        for end in range(len(s)):
            counts[s[end]] += 1
            if end - start + 1 > minSize:
                counts[s[start]] -= 1
                if counts[s[start]] == 0:
                    del counts[s[start]]
                start += 1
            print (counts)
            if end - start + 1 == minSize and len(counts) <= maxLetters:
                substrs[s[start:end+1]] += 1
        print (substrs)
        if not substrs:
            return 0
        return max(substrs.values())
        
        # decrement window until we meet the requirement


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        counter=defaultdict(int)
        
        for i in range(len(s)):
            string=s[i:i+minSize]
            if len(Counter(string))<=maxLetters and len(string)>=minSize:
                counter[string]+=1
        return max(counter.values()) if counter else 0

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # hash table to remember substrings
        substrings = defaultdict(int)
        char_counts = Counter(s[0:minSize-1])
        
        start = 0
        while start <= len(s) - minSize:
            end = start + minSize - 1
            
            end_char = s[end]
            char_counts[end_char] += 1
            
            unique_chars = len(char_counts)
            
            if unique_chars <= maxLetters:
                substrings[s[start:end+1]] += 1

            start_char = s[start]
            if char_counts[start_char] == 1:
                del char_counts[start_char]
            else:
                char_counts[start_char] -= 1
                
            start += 1
            
            
        maxSubstrings = 0
        for substring in substrings:
            if substrings[substring] > maxSubstrings:
                maxSubstrings = substrings[substring]

        return maxSubstrings

class Solution:
    from collections import Counter
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        c = 0
        freq = collections.defaultdict(int)
        for i in range(len(s)-minSize+1):
            p = s[i:i+minSize]
            cur_dict = Counter(p)
            if len(cur_dict) <= maxLetters:
                freq[p] += 1
        if freq:
            return max(freq.values())
        return 0


from collections import Counter
from collections import defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # init first window
        counts = Counter(s[:minSize-1])
        substrs = defaultdict(int)
        start = 0
        # expand window until we can't any more 
        for end in range(minSize-1, len(s)):
            counts[s[end]] += 1
            if end - start + 1 > minSize:
                counts[s[start]] -= 1
                start += 1
            if end - start + 1 == minSize and len(set(counts.elements())) <= maxLetters:
                substrs[s[start:end+1]] += 1
        if not substrs:
            return 0
        return max(substrs.values())
        
        # decrement window until we meet the requirement


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count = defaultdict(int)
        m = 0
        size = minSize
        for i in range(len(s)-size+1):
            word = s[i:i+size]
            if len(Counter(word))<=maxLetters:
                count[word]+=1
                m = max(m,count[word])
        return m


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        # if not s:
        #     return 0
        
        subcount = defaultdict(int)
        
        for i in range(len(s)-minSize+1):
            sub = s[i:i+minSize]
            # print(sub, set(sub))
            if len(set(sub))<=maxLetters:
                subcount[sub]+=1
            # print(sub, set(sub))
                
        # print(subcount)
        x = sorted(subcount.values(), reverse=True)
        if not x:
            return 0
        return x[0]

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        mymap = {}
        
        for i in range(len(s)-minSize+1):
            if len(set(list(s[i:i+minSize]))) <= maxLetters:
                print(s[i:i+minSize])
                if s[i:i+minSize] in mymap:
                    mymap[s[i:i+minSize]] += 1
                else:
                    mymap[s[i:i+minSize]] = 1
        
        if not mymap:
            return 0
        
        return max(mymap.values())

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        res = 0
        count = Counter()
        
        for j in range(len(s) - minSize + 1):
            if len(set(s[j:j+minSize])) > maxLetters:
                continue
            count[s[j:j+minSize]] += 1
            res = max(res, count[s[j:j+minSize]])
        return res

from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        
        # test = Counter(s)
        # print(\"test\", test)
        cnt = Counter()
        word_cnt = Counter()
        cur_hash = 0
#         for i in range(minSize):
#             cnt[s[i]] += 1
#             if len(cnt)>maxLetters:
#                 break
                
        # word_cnt[s[:i+1]] += 1
        # print(word_cnt)
        left = 0
        res = 0
        i = 0
        while i<len(s):
            if i-left+1>minSize:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    del cnt[s[left]]
                left += 1
                
            cnt[s[i]] += 1   
            
            if len(cnt)<=maxLetters and i-left+1==minSize:
                word_cnt[s[left:i+1]] += 1
                # print(s[left:i+1])
                res = max(res, word_cnt[s[left:i+1]])
                
            i += 1
        # print(word_cnt)
        return res
# \"aababcaab\"
# 2
# 3
# 4
# \"aaaa\"
# 1
# 3
# 3
# \"aabcabcab\"
# 2
# 2
# 3
# \"abcde\"
# 2
# 3
# 3
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        res = collections.defaultdict(int)
        for k in range(minSize,minSize+1):
            counter = collections.Counter(s[:k])
            
            for i in range(k,len(s)):
                #print(counter)
                if len(counter.keys())<=maxLetters:
                    res[s[i-k:i]] += 1
                counter[s[i]] += 1
                counter[s[i-k]] -= 1
                if counter[s[i-k]] == 0:
                    del counter[s[i-k]]
            #print(counter)
            
            if len(counter.keys())<=maxLetters:
                res[s[i-k+1:]] += 1
        #print(res)
        return max(res.values()) if res else 0

from collections import Counter
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ## greed algorithm: only focus the substring with length == minSize
        ## also, apply continuous hashing function 
        power = 26 ** (minSize-1)
        cnt = Counter()
        word_cnt = Counter()
        cur_hash = 0
        left = 0
        res = 0
        right = 0
        while right<minSize:
            cnt[s[right]] += 1  
            cur_hash = cur_hash*26 + (ord(s[right]) - ord('a') + 1)
            right += 1
            
        word_cnt[cur_hash] = 1
        while right<len(s):
            if right-left+1>minSize:
                cnt[s[left]] -= 1
                if cnt[s[left]] == 0:
                    del cnt[s[left]]
                cur_hash = cur_hash-power*(ord(s[left]) - ord('a') + 1)
                left += 1
            
            cnt[s[right]] += 1  
            cur_hash = cur_hash*26 + (ord(s[right]) - ord('a') + 1)
            
            if len(cnt)<=maxLetters and right-left+1==minSize:
                word_cnt[cur_hash] += 1
                res = max(res, word_cnt[cur_hash])
                
            right += 1
            
        return res
# \"aababcaab\"
# 2
# 3
# 4
# \"aaaa\"
# 1
# 3
# 3
# \"aabcabcab\"
# 2
# 2
# 3
# \"abcde\"
# 2
# 3
# 3
                


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        tracker = collections.defaultdict(int)
        
        window_tracker = collections.defaultdict(int)
        curr_sum = 0
        
        i = 0
        j = 0
        
        while j < len(s):
            curr = s[j]
            window_tracker[curr] += 1
            curr_sum += 1
            
            # while i < j and (len(window_tracker.keys()) > maxLetters and curr_sum > minSize):
            while i < j and curr_sum > minSize:
                curr_i = s[i]
                curr_sum -= 1
                window_tracker[curr_i] -= 1
                if window_tracker[curr_i] == 0:
                    del window_tracker[curr_i]
                i += 1
            
            temp = collections.defaultdict(int)
            toAdd = s[i:j + 1]
            for char in toAdd:
                temp[char] += 1
            
            if minSize <= curr_sum <= maxSize and len(temp.keys()) <= maxLetters:
                tracker[s[i: j + 1]] += 1
            
            j += 1
        
        print(tracker)
        if len(tracker.values()) == 0:
            return 0
        return max(tracker.values())

from collections import Counter, deque
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        substring = deque([])
        ans = Counter([])
        for ch in s:
            substring.append(ch)
            while len(substring) > minSize:
                substring.popleft()
            cnt = Counter(substring)
            if (len(cnt) <= maxLetters) and (minSize <= len(substring) <= maxSize):
                ans.update({''.join(substring): 1})
        
        return ans.most_common()[0][1] if len(ans) > 0 else 0