Most Frequent Substring Under Distinct-Letter and Length Limits

Given a lowercase string s, consider only the substrings that satisfy two limits, and return how many times the most frequent of them occurs in s.

A substring t of s is eligible when both of the following hold:

• the number of distinct characters in t is at most max_letters;
• the length of t is between min_size and max_size, inclusive.

Return the largest number of occurrences of any eligible substring, or 0 if no substring of s is eligible.

Function Signature

def max_substring_occurrences(s: str, max_letters: int, min_size: int, max_size: int) -> int:

Rules

• Occurrences are counted by starting index. Two occurrences are different if they start at different indices, even when they overlap: in "aaaa", the substring "aaa" starts at indices 0 and 1, so it occurs 2 times.
• Only the count is returned, not the substring, so the answer is a single well-defined integer even when several eligible substrings share the maximum count.

Constraints

• 1 <= len(s) <= 100000
• s contains only lowercase English letters a through z.
• 1 <= max_letters <= 26
• 1 <= min_size <= max_size <= min(26, len(s))
• The answer is an integer between 0 and len(s), inclusive.

Examples

Example 1

Input: s = "aababcaab", max_letters = 2, min_size = 3, max_size = 4

Output: 2

Explanation: "aab" has 2 distinct letters and length 3, and it starts at indices 0 and 6. Every other eligible substring occurs at most twice.

Example 2

Input: s = "aaaa", max_letters = 1, min_size = 3, max_size = 3

Output: 2

Explanation: "aaa" starts at indices 0 and 1; overlapping occurrences both count.

Example 3

Input: s = "abcde", max_letters = 2, min_size = 3, max_size = 3

Output: 0

Explanation: every length-3 substring ("abc", "bcd", "cde") has 3 distinct letters, so no substring is eligible.