We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Occurrences of a Substring

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to find all possible substrings of a certain length (between minSize and maxSize).
  • We must keep track of the number of unique characters in each substring.
  • Using a hash table (dictionary) can help efficiently count occurrences of valid substrings.
  • The sliding window technique can be employed to generate substrings of fixed lengths while maintaining the count of unique characters.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the string and m is the average size of substrings being checked (bounded by maxSize). Space Complexity: O(n), for storing the counts of substrings.

Solution

To solve the problem, we can use a sliding window approach combined with a hash table to count occurrences of valid substrings. We will iterate through the string to extract substrings of lengths defined by minSize and maxSize. For each substring, we will maintain a count of unique characters and only consider it if it meets the maxLetters constraint. The hash table will help us keep track of how many times each valid substring occurs.

Code Solutions

def maxFreq(s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    from collections import defaultdict
    
    substring_count = defaultdict(int)
    n = len(s)
    
    for size in range(minSize, maxSize + 1):
        for i in range(n - size + 1):
            substring = s[i:i + size]
            unique_chars = set(substring)
            if len(unique_chars) <= maxLetters:
                substring_count[substring] += 1
    
    return max(substring_count.values(), default=0)
← Back to All Questions