Maximum Number of Occurrences of a Substring — LeetCode 1297 Python Solution

The problem

Given a string s, return the maximum number of occurrences 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

Input

s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4

Output

2

Explanation

Substring "aab" has 2 occurrences in the original string.

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1297. Maximum Number of Occurrences of a Substring is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems