题目重点：长度在 [minLength,maxLength] 且至多 maxUnique 种字符的子串中，求最大出现次数；证明只查 minLength 即可，覆盖 10 万字符规模。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 子串按起点/终点计出现次数，重叠出现分别计数；只返回最大频次，不需返回对应文本。
- 1≤minLength≤maxLength；若字符串短于 minLength，答案为 0。
- 字符按 Python Unicode code point 区分；题目没指定大小写归一化或 grapheme 规则。
解题路线
- 先看任意合法长子串 S（长度 L≥minLength）出现 f 次。取其前 minLength 个字符 P：S 每一次出现，都对应 P 在同一位置出现；所以 P 的出现次数至少 f。P 的不同字符数不超过 S，因而也合法。
- 因此某个最优值总可由长度恰好 minLength 的子串达到；无需枚举 minLength..maxLength 的所有长度。
- 扫所有长度 minLength 的窗口，若不同字符数≤maxUnique，就用哈希表累计该窗口文本；返回最大计数。
- minLength≤26 时直接切片并建 set 简洁且上界可控；若窗口很大，可用滑动频次维护 distinct count，但仍需对窗口内容做稳定 key（哈希或滚动哈希加冲突核验）。
手动走一遍
abcde、长度 2..4、maxUnique≥4：长度 2 的 ab/bc/cd/de 各一次，答案 1。若 text=aaaa、minLength=2，aa 在起点 0、1、2 重叠出现三次；长度 3 的 aaa 只出现两次，说明只看最短长度仍能达到最大。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
def max_valid_substring_frequency(text: str, min_length: int, max_length: int, max_unique: int) -> int:
"""Return the largest frequency of a valid substring."""
if min_length < 1 or max_length < min_length or max_unique < 0:
raise ValueError("invalid limits")
if len(text) < min_length:
return 0
counts: Counter[str] = Counter()
for left in range(len(text) - min_length + 1):
candidate = text[left:left + min_length]
if len(set(candidate)) <= max_unique:
counts[candidate] += 1
return max(counts.values(), default=0)
if __name__ == "__main__":
assert max_valid_substring_frequency("abcde", 2, 4, 5) == 1
复杂度
设 n 为字符串长度、m 为 minLength。每个窗口切片与建 set O(m)，共 O(nm) 时间；字典最坏保存 O(n) 个长度 m 的字符串，字符存储 O(nm)。由题目 maxLength≤26 可知 m≤26，因此在该约束下时间约 O(26n)。哈希表预期操作 O(1)，碰撞极端情况另论。
易错点与追问
容易失分的边界
- 把 maxLength≤26 当成字符串长≤26；题目 n 可到 10^5。
- 把重叠出现只算一次。
- 只看最短长度却不给正确性理由；关键是长子串每次出现映射到合法的短前缀。
- 不同字符数超标时仍把候选加到频次表。
- 声明代码额外空间仅 O(n)，忽略字典键字符串长度。
继续深挖
- 若要返回所有并列最高频子串，字典如何收集并排序？
- 若不同字符约束改为恰好 maxUnique，最短前缀的证明还成立吗？
- 若要支持多次不同 minLength 的查询，预处理应如何权衡内存？
