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
Given a string `s` of lowercase English letters and integers `min_length`, `max_length` and `max_unique`, consider every substring of `s` 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`.
### 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.
- The answer lies between `0` and `len(s)`, so it never exceeds 2^31-1 and fits in a 32-bit `int` in every language.
### 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.
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.
- The answer lies between 0 and len(s), so it never exceeds 2^31-1 and fits in a 32-bit int in every language.
Examples
Input: ('z', 1, 1, 1)
Expected Output: 1
Explanation: Minimum valid input: one character with min_length = max_length = 1; 'z' occurs once.
Input: ('abcde', 2, 4, 26)
Expected Output: 1
Explanation: Source Example 1: max_unique = 26 excludes nothing and every substring of length 2-4 occurs exactly once.
Hints
- Occurrences may overlap: count a substring once for every starting position where it appears, as in "aaa" where "aa" occurs 2 times.
- A substring must meet both conditions at once: its length lies in [min_length, max_length] and it has at most max_unique distinct characters.
- If no substring meets both conditions (for example when min_length is greater than len(s)), the answer is 0.