Maximum Number of Occurrences of a Substring LeetCode solution in Python

1
#   0   1   2   3
2
#   a   a   a   a
3
#   l
4
#   r
5

6
# ref: https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457577/C%2B%2B-Greedy-approach-%2B-Sliding-window-O(n).
7

8
# Intuition
9
# if a string have occurrences x times, any of its substring must also appear at least x times
10
# there must be a substring of length minSize, that has the most occurrences
11
# so that we just need to count the occurrences of all substring with length minSize
12

13

14
# Explanation
15
# find the maximum occurrences of all substrings with length = minSize
16
class Solution:
17
    # T=O(n), S=O(n)
18
    # use sliding window to lock down substrings to minSize limit (greedy approach)
19
    # then use a counter to count the occurences of valid substrings
20
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
21
        # dict to store valid substrings and their respective occurences count
22
        d = defaultdict(int)
23
        # find longest substrings that has k unique chars
24
        # counter dict for char count and make sure unique char count is not exceeded
25
        counter = defaultdict(int)
26
        # init left and right pointers of sliding window
27
        r = l = 0
28
        # iterate right pointer
29
        while r < len(s):
30
            counter[s[r]] += 1
31

32
            # invalid window found, so make it valid again
33
            # len of window is greater than minSize
34
            while (r - l + 1) > minSize:
35
                counter[s[l]] -= 1
36
                # remove the key from dict for unique char count if it becomes zero
37
                if counter[s[l]] == 0:
38
                    del counter[s[l]]
39
                # increment the left pointer to make it a valid window
40
                l += 1
41

42
            # valid window size (minSize) and unique char count is lesser than or equal to maxLetters
43
            if r - l + 1 == minSize and len(counter) <= maxLetters:
44
                # increment count of the occurence of the substring
45
                d[s[l : r + 1]] += 1
46

47
            # make sure to update right pointer only after an iteration
48
            r += 1
49

50
        # return the count of substring with max occurence
51
        # edge case with no substring
52
        return max(d.values()) if d else 0