Most Frequent Substring Under Distinct-Letter and Length Limits
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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.
Overview: Find how often the most frequent eligible substring appears in a lowercase string, where an eligible substring has a length within a given range and no more than a set number of distinct letters. Overlapping occurrences count and inputs reach 100,000 characters, so the task tests efficient substring counting.