Problem Breakdown
We are given a string s and need to find the maximum frequency of any substring that satisfies two specific constraints:
- Length Constraint: The substring length must be within
[minSize, maxSize]. - Uniqueness Constraint: The number of unique characters in the substring cannot exceed
maxLetters.
Inputs & Outputs:
- Input: String
s, integersmaxLetters,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 .
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 substrings for each valid size up to maxSize. If we naively checked all lengths independently, the complexity would be proportional to .
Key Insight:
Consider a substring of length 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 , 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 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
- Initialize a hash map (or
Counter) to store frequency counts for substrings of length exactlyminSize. - Iterate through the string from index up to
len(s) - minSize + 1. This ensures we can extract at least one substring of lengthminSizestarting at each position. - For each iteration, slice the substring:
sub = s[i : i+minSize]. - Check if the number of unique characters in
subis . This check takes time using a set or bit manipulation (since alphabet size is small). - If valid, increment its count in the map.
- After iterating through all positions, return the maximum value from the frequency map. Use
default=0to handle cases where no substrings are valid.
Complexity Analysis
- Time Complexity: , where is the length of string
sand . Since we iterate through each character once () 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: , where is the number of unique valid substrings found. Given
minSize, 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 ().
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_mapremains 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 . - 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
minSizeis sufficient, so explicit iteration up tomaxSizeis not needed in code for performance optimization.