#1297

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Maximum Number of Occurrences of a Substring

Find the maximum number of occurrences of any valid substring in a given string with specific constraints on letter count and length.

hash table string sliding window

Problem Statement

Given a string s, return the maximum number of occurrences of any substring that adheres to the following conditions. The substring's length should be between minSize and maxSize, and the substring must contain at most maxLetters distinct characters.

You need to efficiently count how many times valid substrings occur, ensuring that you track the valid ones that meet the constraints without checking all possibilities explicitly. Pay attention to the time complexity, especially given that the length of s can be large.

Examples

Example 1

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4

Output: 2

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

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.

Solution Approach

Sliding Window Approach

Use a sliding window to traverse through the string s and generate all possible substrings of lengths between minSize and maxSize. For each window, maintain a count of distinct characters and update it dynamically as the window slides.

Efficient Frequency Counting with Hash Table

Use a hash table (or dictionary) to keep track of the frequency of each valid substring. For each substring in the sliding window, check its occurrence and update the maximum count if it’s valid (i.e., respects the distinct letter and length constraints).

Optimized Memory Management

Optimize memory usage by clearing or updating only necessary data points during the sliding window process. This prevents storing too many intermediate substrings and reduces space complexity while ensuring efficient checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the size of the input string and the constraints on substring length and distinct characters. With an efficient sliding window and hash table update mechanism, the overall time complexity is reduced from a brute force O(n^3) to something more manageable. Space complexity depends on the number of distinct substrings tracked during the sliding window, which can be limited by maxLetters and the substring length constraints.

What Interviewers Usually Probe

Understanding of sliding window techniques for substring problems.
Ability to optimize using hash tables and efficiently track occurrences.
Awareness of the trade-offs between time and space complexity for large input sizes.

Common Pitfalls or Variants

Common pitfalls

Not correctly handling overlapping substrings or missing edge cases related to character constraints.
Failure to manage space complexity when storing intermediate substrings, especially when maxSize is large.
Overcomplicating the solution with unnecessary checks or calculations when simpler, more efficient approaches exist.

Follow-up variants

Adjusting the constraints, such as reducing maxLetters or changing minSize, to test the robustness of the solution.
Adapting the solution to handle strings with only one character type (e.g., all 'a's).
Modifying the problem to count substrings that meet additional conditions, such as having even or odd length.

FAQ

What is the most efficient way to solve the Maximum Number of Occurrences of a Substring problem?

The most efficient solution uses a sliding window technique with hash table frequency tracking, ensuring that only valid substrings are considered, optimizing both time and space complexities.

How can I optimize the space complexity for this problem?

By managing the hash table carefully, clearing or updating it only when necessary, and reducing redundant calculations during each sliding window movement.

Can substrings overlap in this problem?

Yes, substrings can overlap. The solution should correctly count all valid occurrences, even if the substrings share characters.

What happens if `maxSize` is smaller than `minSize`?

The constraints would be invalid. Ensure that maxSize is always greater than or equal to minSize for a valid solution.

How does the sliding window work in this problem?

The sliding window generates substrings of different lengths, keeping track of distinct letters and their frequencies to ensure they meet the constraints of maxLetters and valid size ranges.

terminal

Solution

Solution 1: Hash Table + Enumeration

According to the problem description, if a long string meets the condition, then its substring of length $\textit{minSize}$ must also meet the condition. Therefore, we only need to enumerate all substrings of length $\textit{minSize}$ in $s$, then use a hash table to record the occurrence frequency of all substrings, and find the maximum frequency as the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ans = 0
        cnt = Counter()
        for i in range(len(s) - minSize + 1):
            t = s[i : i + minSize]
            ss = set(t)
            if len(ss) <= maxLetters:
                cnt[t] += 1
                ans = max(ans, cnt[t])
        return ans

Solution 2: Sliding Window + String Hashing

We can use a sliding window to maintain the number of distinct letters in the current substring, while using string hashing to efficiently calculate the hash value of substrings, thereby avoiding using strings as hash table keys and improving performance.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ans = 0
        cnt = Counter()
        for i in range(len(s) - minSize + 1):
            t = s[i : i + minSize]
            ss = set(t)
            if len(ss) <= maxLetters:
                cnt[t] += 1
                ans = max(ans, cnt[t])
        return ans

Continue Practicing

#1358 number of substrings containing all three characters #1156 swap for longest repeated character substring #1016 binary string with substrings representing 1 to n