Skip to content

1423. Maximum Number Of Occurrences Of A Substring

Hash Table String Sliding Window

Problem - Maximum Number Of Occurrences Of A Substring

Medium

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

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 occurrences 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.

 

Constraints:

  • 1 <= s.length <= 105
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)
  • s consists of only lowercase English letters.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        result = 0
        count = Counter()

        for i in range(len(s) - minSize + 1):
            temp = s[i : i + minSize]
            string_set = set(temp)
            if len(string_set) <= maxLetters:
                count[temp] += 1
                result = max(result, count[temp])

        return result

Submission Stats:

  • Runtime: 110 ms (44.81%)
  • Memory: 19.3 MB (89.72%)