Meta 恰好n种字符的最短子串：收缩到失去可行性

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• n必须正数；按Unicode code point计字符，返回最短子串，等长选最早出现；不存在返回None。
• 实际题若只给英文字母可换固定数组。字形簇和大小写归一化需要另行定义，示例不隐式转换。

解题路线

1. 用计数字典追踪窗口每字符频次。右端扩张后，只要种类数>=n就尝试收缩；恰好n时先记录候选，再删左端一个字符。
2. 种类数>n时不记录答案，继续收缩直到恰好；恰好n阶段也继续收缩，找到该右端的最短合法窗口，再跨过失效边界。
3. 每次删到频次0移除字典key；不移除会把消失的字符继续算成一种。更新仅在更短时发生，所以等长保留最早候选。

手动走一遍

aaabcc，n=2，最短候选ab与bc都长2，返回ab；n=3返回abc；n=4返回None。n=1时任一单字符最优，返回第一个字符。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def shortest_distinct_substring(text, n):
    """Return earliest shortest substring with exactly n distinct Unicode code points."""
    if n <= 0:
        raise ValueError("n must be positive")
    counts = {}
    left = 0
    best = None
    for right, char in enumerate(text):
        counts[char] = counts.get(char, 0) + 1
        while len(counts) >= n:
            if len(counts) == n and (best is None or right + 1 - left < best[1] - best[0]):
                best = (left, right + 1)
            old = text[left]; counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
    return None if best is None else text[best[0]:best[1]]

复杂度

O(|text|)预期时间，每端只推进一次；字符计数空间O(min(|text|,alphabetSize))，输出子串切片O(L)。

易错点与追问

容易失分的边界

• 求最长至多n种字符的标准滑窗只在超n时收缩，不能直接得到最短恰好n的答案。
• 只保存set无法知道删除一个字符后它是否仍存在窗口中。

继续深挖

• 若要求恰好n种且每种至少出现m次，需维护达到m的种类数，收缩条件不能只看字典大小。
• 若流式输入只要求长度，可不保存最终文字，但仍要能移除左端字符；若输出文字需要保留对应窗口。