Most Frequent Substring Within a Length Range and a Distinct-Letter Limit

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

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

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

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

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.