Most Frequent Substring Within a Length Range and a Distinct-Letter Limit
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given a string `s`, consider every substring whose length is between `min_length` and `max_length` (inclusive) and that contains at most `max_unique` distinct characters. Return the number of times the most frequent such substring occurs in `s`.
### Function Signature
```python
def max_substring_frequency(s: str, min_length: int, max_length: int, max_unique: int) -> int:
```
### Rules
- A substring is a non-empty run of consecutive characters of `s`. Two substrings are the same substring when they have the same characters in the same order, wherever they start.
- Occurrences are counted at every starting position, so they may overlap: in `"aaa"`, the substring `"aa"` occurs 2 times.
- A substring qualifies when its length `L` satisfies `min_length <= L <= max_length` and it contains at most `max_unique` distinct characters.
- Return the largest occurrence count of any qualifying substring. Substrings of different lengths are counted separately and compete for the same maximum.
- Return `0` if no substring qualifies, including when `min_length` is greater than `len(s)`.
### Constraints
- `1 <= len(s) <= 10^5`
- `s` consists only of lowercase English letters `'a'` to `'z'`.
- `1 <= min_length <= max_length <= 26`
- `1 <= max_unique <= 26`. A value of 26 places no restriction, because `s` has at most 26 distinct characters.
### Examples
**Example 1**
```text
Input: s = "abcde", min_length = 2, max_length = 4, max_unique = 26
Output: 1
```
Every substring of length 2, 3 or 4 occurs exactly once, and the distinct-character limit excludes nothing.
**Example 2**
```text
Input: s = "aaaba", min_length = 2, max_length = 3, max_unique = 1
Output: 2
```
Only substrings made of one repeated character qualify. `"aa"` starts at positions 0 and 1, so it occurs 2 times even though the two occurrences overlap, and `"aaa"` occurs once. `"ab"`, `"ba"`, `"aab"` and `"aba"` contain two distinct characters and do not qualify.
**Example 3**
```text
Input: s = "abab", min_length = 2, max_length = 3, max_unique = 1
Output: 0
```
Every substring of length 2 or 3 contains both `'a'` and `'b'`, so none qualifies.
Overview: A string coding problem: among all substrings whose length falls in a given range and that use at most a given number of distinct letters, return how many times the most frequent one occurs. It tests handling overlapping occurrences and the distinct-letter limit, counting efficiently on strings of up to 100,000 characters, and returning zero when nothing qualifies.
Read the full Microsoft Software Engineer interview experience this question came from