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.
Given a string `s` of lowercase English letters and three integers `max_letters`, `min_size` and `max_size`, consider only the substrings of `s` 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.
Implement `max_substring_occurrences(s, max_letters, min_size, max_size)`, which returns an integer.
### 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.
### 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.
### 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, so it never exceeds 2^31 - 1 and fits in a 32-bit `int` in every language.
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; it never exceeds 2^31 - 1, so a 32-bit int suffices in every language.
Examples
Input: ('a', 1, 1, 1)
Expected Output: 1
Explanation: Minimum valid input: the one-letter substring 'a' is eligible and occurs once.
Input: ('abc', 3, 3, 3)
Expected Output: 1
Explanation: min_size = max_size = len(s): the whole string is the only candidate, and its 3 distinct letters equal max_letters, so it is eligible once.
Hints
- Occurrences are counted by starting index, so overlapping copies of the same substring each count separately.
- Both limits must hold at once: a substring of allowed length with too many distinct letters is not eligible, and neither is a substring with few letters but a length outside [min_size, max_size].
- Only the count is returned, so when several eligible substrings tie for the most occurrences, it does not matter which one you pick.