Domain 2MediumMEDIUM

Maximum Number of Occurrences of a Substring

LeetCode problem 1297: Maximum Number of Occurrences of a Substring (medium).

Domain: medium•Updated: 2026-09-14
#String#Bit Manipulation

Problem Breakdown

We are given a string s and need to find the maximum frequency of any substring that satisfies two specific constraints:

  1. Length Constraint: The substring length must be within [minSize, maxSize].
  2. Uniqueness Constraint: The number of unique characters in the substring cannot exceed maxLetters.

Inputs & Outputs:

  • Input: String s, integers maxLetters, minSize, maxSize.
  • Output: Integer representing the maximum occurrence count found among all valid substrings. If no such substring exists, return 0.

Edge Cases & Constraints:

  • Overlapping Occurrences: Allowed (e.g., “aaaa” with min=3 counts overlapping instances).
  • No Valid Substring: Return 0 if the map of frequencies is empty after processing.
  • String Length vs Max Size: The constraint maxSize <= min(26, s.length) implies that valid substrings are relatively short (bounded by alphabet size or explicit limit), which simplifies hashing and complexity analysis compared to general string problems where length could be O(N)O(N).

Intuition

A brute-force approach would iterate through every possible substring within the range [minSize, maxSize], check its unique character count, and update a frequency map. This results in checking roughly (N−min+1)(N - min + 1) substrings for each valid size up to maxSize. If we naively checked all lengths L∈[minSize,maxSize]L \in [minSize, maxSize] independently, the complexity would be proportional to ∑L=minmax(N−L)\sum_{L=min}^{max} (N-L).

Key Insight: Consider a substring of length L>minSizeL > minSize that satisfies the unique character constraint. Any prefix or suffix of this string with length minSize also starts/ends at the same index and contains a subset of characters from the longer string. Since the parent has ≤maxLetters\le maxLetters, any sub-segment must strictly have fewer (or equal) unique characters, thus satisfying the condition automatically.

Therefore, every occurrence found for a substring in [min+1, maxSize] implies an occurrence of its corresponding prefix/suffix of length minSize. Consequently, counting occurrences only for substrings of exactly length minSize is sufficient to determine the maximum frequency among all valid lengths. If a longer string occurs kk times, its shorter counterpart (prefix) also starts at those indices and will be counted in our map. Since we want the maximum count, checking just the smallest valid length captures all potential frequencies because any occurrence of a larger valid substring is “covered” by an occurrence of a smaller one starting at the same position.

Approach

  1. Initialize a hash map (or Counter) to store frequency counts for substrings of length exactly minSize.
  2. Iterate through the string from index 00 up to len(s) - minSize + 1. This ensures we can extract at least one substring of length minSize starting at each position.
  3. For each iteration, slice the substring: sub = s[i : i+minSize].
  4. Check if the number of unique characters in sub is ≤maxLetters\le maxLetters. This check takes O(minSize)O(minSize) time using a set or bit manipulation (since alphabet size is small).
  5. If valid, increment its count in the map.
  6. After iterating through all positions, return the maximum value from the frequency map. Use default=0 to handle cases where no substrings are valid.

Complexity Analysis

  • Time Complexity: O(N⋅K)O(N \cdot K), where NN is the length of string s and K=minSizeK = minSize. Since we iterate through each character once (O(N)O(N)) and perform a set construction on a substring of bounded size (max 26 characters per constraint), this effectively simplifies to linear time relative to input size.
  • Space Complexity: O(M⋅K2)O(M \cdot K^2), where MM is the number of unique valid substrings found. Given minSize ≤maxSize≤26\le maxSize \le 26, the storage for each key in the map is small constant space per entry. In practice, this fits well within memory limits even for large strings because distinct short substrings are limited by combinatorics (≈26maxLetters\approx 26^{maxLetters}).

Solution

import collections

def maxFreq(s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    # Frequency map to store counts of valid substrings with length = minSize.
    count_map = collections.Counter()
    
    n = len(s)
    # Iterate through all possible starting positions for a substring of length minSize.
    # We stop at n - minSize + 1 because s[i : i+minSize] must be valid slice.
    for i in range(n - minSize + 1):
        sub = s[i : i + minSize]
        
        # Check unique character constraint efficiently using set length.
        if len(set(sub)) <= maxLetters:
            count_map[sub] += 1
            
    # Return the maximum frequency found, or 0 if no valid substring exists.
    return max(count_map.values(), default=0)

Edge Cases Handled

  • No Valid Substrings: If count_map remains empty (e.g., all substrings violate unique char constraint), max(..., default=0) correctly returns 0.
  • String Length < minSize: The loop range becomes invalid or empty (range(0)), resulting in an empty map and returning 0, which is correct behavior though constraints guarantee s.length≥minSizes.length \ge minSize.
  • Overlapping Occurrences: Since we iterate every index i, overlapping instances (like “aaa” with size 3) are counted correctly at each start position.
  • Max Size Constraint Ignored: The logic implicitly handles the fact that checking only minSize is sufficient, so explicit iteration up to maxSize is not needed in code for performance optimization.