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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

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:
		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
				elif 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):
			for i in range(left, right, 1):
				if right - i < minSize:
					break
				valid_str = s[i:right]
				valid_str_freq[valid_str] += 1
				res = max(res, valid_str_freq[valid_str])
			if s[right] not in window_letter:
				window_letter[s[right]] = 1
			else:
				window_letter[s[right]] += 1
			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]
			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
		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:
		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
			for l in range(minSize, maxSize):
				beg = j - l + 1
				if beg >= i:
					ans[s[beg:j + 1]] += 1
		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
				letters_tmp[s[j_tmp]] -= 1
				if letters_tmp[s[j_tmp]] == 0:
					unique_tmp -= 1
				j_tmp += 1
			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
				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
			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]])
		return res


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:
		counts = {}
		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
				c = s[i]
				window[c] = window.get(c, 0) + 1
				if start >= 0:
					c = s[start]
					window[c] -= 1
					if window[c] == 0:
						del window[c]
				if len(window) <= maxLetters:
					sub = s[start + 1:i + 1]
					counts[sub] = counts.get(sub, 0) + 1
		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))
		while st + minSize <= n:
			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


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
		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:
		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:
					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:
					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:
		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
				M[s[i - size]] -= 1
				if M[s[i - size]] == 0:
					del M[s[i - size]]
				M[c] += 1
			if len(M) <= maxLetters:
				res[s[n - size:]] += 1
			size += 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:
		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]
				if len(set(ss)) <= maxLetters:
					freq[ss] += 1
					best = max(best, freq[ss])
		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:
					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:
		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
		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])


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
		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:
		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
		return max(cache.values()) if cache else 0


class Solution:

	def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
		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]
				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
		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):
			for j in range(i + minSize - 1, min(i + maxSize, n)):
				if len(set(s[i:j + 1])) <= maxLetters:
					d[s[i:j + 1]] += 1
		if d:
			return max(d.values())
		return 0


class Solution:

	def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
		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])
		return ans


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):
				if j <= len(s):
					substr = s[i:j]
					if len(set(substr)) <= maxLetters:
						if substr in dict:
							dict[substr] += 1
						else:
							dict[substr] = 1
		max_count = 0
		for (k, v) in list(dict.items()):
			max_count = max(max_count, v)
		return max_count


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


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
				if len(set(s_s)) <= maxLetters:
					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:
		currDct = {}
		ansDct = defaultdict(int)
		length = len(s)
		l = 0
		r = 0
		while l + minSize < length + 1:
			currDct = Counter(s[l:l + minSize])
			if len(currDct) <= maxLetters:
				ansDct[s[l:l + minSize]] += 1
			else:
				l += 1
				continue
			if minSize == maxSize:
				l += 1
				continue
			r = l + minSize + 1
			while r < length and r < l + maxSize:
				currDct[s[r]] += 1
				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
		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
		if list(counter.values()) == []:
			return 0
		return max(counter.values())


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
			elif 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:
		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
		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:
					seen[hash] += 1
					ans = max(ans, seen[hash])
		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]])
		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):
			q = deque()
			for i in range(0, len(s)):
				q.append(s[i])
				if i > size - 1:
					q.popleft()
				if i >= size - 1 and len(set(q)) <= maxLetters:
					count[tuple(q)] += 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:
		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]
				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
			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])
		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:
		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):
				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
		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
		return max(substr.values(), default=0)


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:
		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
		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
				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()
		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


import collections

class Solution:

	def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
		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)
		uniqSubStrDict = {}
		count = 0
		Max = 0
		for i in range(minSize, maxSize + 1):
			for j in range(lenS - i + 1):
				tstSubStr = s[j:j + i]
				uniqChars = {}
				for k in tstSubStr:
					uniqChars[k] = 1
				if len(uniqChars) > maxLetters:
					continue
				uniqSubStrDict[tstSubStr] = uniqSubStrDict.get(tstSubStr, 0) + 1
				if uniqSubStrDict[tstSubStr] > Max:
					Max = uniqSubStrDict[tstSubStr]
		count = Max
		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
			elif 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:
		hashmap = {}
		occ = {}
		for i in range(len(s)):
			hashmap[s[i]] = hashmap.get(s[i], 0) + 1
			if i >= minSize:
				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:
		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
			if count <= maxLetters:
				counter[s[i:i + minSize]] += 1
		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
			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
			reader += 1
		if not substring_count:
			return 0
		return max(substring_count.values())


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:
		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):
				res[s[i:j + 1]] = res.get(s[i:j + 1], 0) + 1
				map1[s[i]] = map1[s[i]] - 1
				if map1[s[i]] == 0:
					del map1[s[i]]
				i = i + 1
			j = j + 1
		if len(res) == 0:
			return 0
		else:
			maximum = max(res, key=res.get)
			return res[maximum]


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:
		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())


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


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


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
			elif 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())


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])
		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)):
			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


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


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:
		counts = defaultdict(int)
		substrs = defaultdict(int)
		start = 0
		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())


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:
		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


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:
		subcount = defaultdict(int)
		for i in range(len(s) - minSize + 1):
			sub = s[i:i + minSize]
			if len(set(sub)) <= maxLetters:
				subcount[sub] += 1
		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:
		cnt = Counter()
		word_cnt = Counter()
		cur_hash = 0
		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
				res = max(res, word_cnt[s[left:i + 1]])
			i += 1
		return res


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)):
				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]]
			if len(counter.keys()) <= maxLetters:
				res[s[i - k + 1:]] += 1
		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:
		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


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