1297. Maximum Number of Occurrences of a Substring - Detailed Explanation

Problem Statement

Description:
Given a string s and three integers maxLetters, minSize, and maxSize, find the maximum number of occurrences of any substring of s that meets the following conditions:

• The substring’s length is between minSize and maxSize (inclusive).

• The substring contains at most maxLetters unique characters.

Return the maximum number of occurrences among all such substrings. If no substring meets the conditions, return 0.

Examples:

1. Example 1:

   • Input:
     s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
   • Output: 2
   • Explanation:
     The substring "aab" appears 2 times and contains 2 unique letters which is within the allowed limit. Although "aba" also appears, its frequency is lower.

2. Example 2:

   • Input:
     s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
   • Output: 2
   • Explanation:
     The substring "aaa" appears 2 times and contains only 1 unique letter, satisfying the condition.

3. Example 3:

   • Input:
     s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
   • Output: 0
   • Explanation:
     No substring of length 3 in "abcde" contains at most 2 distinct letters since all such substrings have 3 distinct letters.

Constraints:

• The length of s is up to 10^5.
• 1 <= maxLetters, minSize, maxSize <= s.length
• The string s consists of lowercase English letters.

Hints Before the Solution

1. Sliding Window Insight:
   Consider using a sliding window to efficiently count substrings of fixed length (minSize). Notice that if a longer substring satisfies the condition, its shorter substring (of length minSize) is also valid and will have a higher occurrence frequency.

2. Unique Characters Count:
   Use a frequency count (or set) to determine the number of unique letters in the current window. This will help you quickly check if the substring meets the maxLetters condition.

Approaches

Approach 1: Brute Force

Idea:

• Generate every possible substring with lengths from minSize to maxSize.
• For each substring, count the unique letters.
• If the substring meets the condition (unique count ≤ maxLetters), record its frequency.
• Finally, return the maximum frequency found.

Issues:

• This approach involves nested loops and checking many substrings, which can be very slow (O(n²) or worse) for large strings.

When to use:

• Only for very small inputs or for understanding the problem logic.

Approach 2: Optimal Sliding Window (Using Fixed Window of Length minSize)

Observation:

• Although the allowed substring length can range up to maxSize, it turns out that the optimal candidate is always of length minSize.
  Reason: If a longer substring satisfies the condition, its substring of length minSize will also satisfy the condition and will appear more frequently.

Steps:

1. Initialize a sliding window of size minSize.

2. For each window:

   • Count the number of unique letters.
   • If the unique count is ≤ maxLetters, add (or update) the frequency of that substring in a dictionary.

3. Return the highest frequency from the dictionary.

Advantages:

• This approach only requires scanning the string once, making it O(n) in time.

Code Solutions

Python Implementation