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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Occurrences of a Substring

Number: 1423

Difficulty: Medium

Paid? No

Companies: Salesforce, Hubspot, Addepar, Atlassian, Roblox

Problem Description

Given a string s, determine the maximum frequency of any substring that satisfies two conditions: (1) it has at most maxLetters unique characters and (2) its length is between minSize and maxSize (inclusive). Note that substrings may overlap.

Key Insights

  • Only substrings of length minSize need to be considered. Increasing the substring length tends to decrease frequency, so minSize is optimal.
  • A sliding window can efficiently generate all substrings of the required fixed length.
  • Use a hash table (dictionary) to count frequencies of the valid substrings.
  • Use another frequency dictionary or counter to maintain counts of unique letters in the sliding window for efficient updates.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string s, since we slide a window of fixed length (minSize) over s. Space Complexity: O(n) in the worst-case scenario for storing substring counts, although it is bounded by the number of possible substrings considering the constraints.

Solution

We solve the problem by focusing on substrings of exactly minSize. This is because a longer substring is less frequent, so to maximize frequency, we should choose the smallest size allowed (minSize). We slide a window of length minSize across s, and for each window, maintain a count of characters using a hash table for efficient unique character counting. If the window contains at most maxLetters unique characters, we add it to our frequency dictionary. Finally, we iterate over the dictionary to find the maximum frequency among valid substrings.

The main data structures used include:

  • Two hash tables (dictionaries): one for the current window’s character frequency and one for counting valid substring occurrences.
  • A sliding window approach is used to update substrings in O(1) per move (by adjusting counts for the exiting and entering characters).

Code Solutions

# Python solution with line-by-line comments

def maxFreq(s, maxLetters, minSize, maxSize):
    # Dictionary to count frequency of valid substrings of length minSize
    substring_count = {}
    # Dictionary to maintain frequency of characters in the current window
    current_window = {}
    n = len(s)
    
    # Initialize the current window with the first minSize characters
    for i in range(minSize):
        current_window[s[i]] = current_window.get(s[i], 0) + 1

    # Check the first window if valid and update substring_count
    if len(current_window) <= maxLetters:
        substring = s[:minSize]
        substring_count[substring] = substring_count.get(substring, 0) + 1

    # Slide the window from index 1 to n - minSize
    for i in range(1, n - minSize + 1):
        # Remove the outgoing character from the window
        outgoing_char = s[i - 1]
        current_window[outgoing_char] -= 1
        if current_window[outgoing_char] == 0:
            del current_window[outgoing_char]
        
        # Add the new incoming character
        incoming_char = s[i + minSize - 1]
        current_window[incoming_char] = current_window.get(incoming_char, 0) + 1
        
        # Check if the window is valid based on maxLetters constraint
        if len(current_window) <= maxLetters:
            substring = s[i:i + minSize]
            substring_count[substring] = substring_count.get(substring, 0) + 1
    
    # Return the maximum frequency found, or 0 if none
    return max(substring_count.values()) if substring_count else 0

# Example usage:
print(maxFreq("aababcaab", 2, 3, 4))
← Back to All Questions