Maximum Number of Occurrences of a Substring

Intuition

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.

Solution


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