First key point is that, if there are m same substring with length l, there must be at least m same substring with length l - 1. Since we only need to get the most frequenct substring, we only need to consider substring with the minSize.
There are totally len(s) - minSize + 1 of substrings with length minSize. Since we are given that minSize <= 26, the time complexity to group those substrings is O(n * 26).
So we could groups those possible substrings and return the size of largest group.
import string
from collections import defaultdict
class Solution:
def maxFreq(self, s, maxLetters, minSize, maxSize):
base = ord('a')
value = []
tmp = 1
for _ in range(26):
value.append(tmp)
tmp = tmp << 1
counts = defaultdict(int)
for i in range(len(s) - minSize + 1):
letters = 0
count = 0
sub = s[i:i + minSize]
for c in sub:
if not (letters & value[ord(c) - base]):
letters = letters | value[ord(c) - base]
count += 1
if count <= maxLetters:
counts[sub] += 1
return max(list(counts.values()) + [0])