Nvidia 最长无重复子串：滑动窗口与最早并列答案

题意与假设

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

• 训练版输入 Python 字符串，字符按 Unicode code point 比较；返回 `(最大长度, 最早出现的最长子串)`。题目未规定返回结构或并列策略。
• 空串返回 `(0, '')`；大小写和不同 code point 视为不同字符，不做 Unicode 规范化。
• 若面试官只要长度，保留长度即可；若按 grapheme cluster 比较，须先用合适的文本分段库，与本实现语义不同。

解题路线

1. 维护窗口 `[left,right]`，其中每个字符至多出现一次；哈希表记录字符上次位置。每读新字符，若它在当前窗口内出现过，把 left 移到上次位置后一位。
2. left 只能右移，不能回退。更新字符最新位置后，当前窗口仍无重复；这是每步的不变量。每个 right 的最早可行 left 使该 right 的窗口最长，因此扫描所有 right 可覆盖全局最优。
3. 只在新窗口严格长于记录时更新答案，保留最早出现的并列最长子串；最后用起点和长度切片。

手动走一遍

`abba`：读到前两个字符时窗口为 `ab`、长度 2；第二个 `b` 让 left 跳到下标 2，窗口变 `b`；最后 `a` 得到 `ba`、长度同为 2。因并列取最早，返回 `(2,'ab')`。

Python 参考实现

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

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

"""Return the earliest longest substring with no repeated Unicode code points."""


def longest_unique_substring(text):
    last_seen = {}
    left = 0
    best_start = 0
    best_length = 0
    for right, char in enumerate(text):
        previous = last_seen.get(char, -1)
        if previous >= left:
            left = previous + 1
        last_seen[char] = right
        length = right - left + 1
        if length > best_length:
            best_start, best_length = left, length
    return best_length, text[best_start:best_start + best_length]

复杂度

字符串长度 N、不同字符数 U：扫描 O(N)，保存上次位置 O(U)，最终切片最多 O(N)。Python 字符串下标按 code point 工作；处理组合字符或 emoji 序列时用户感知字符可能与下标单位不同。

易错点与追问

容易失分的边界

• 发现重复字符时无条件设 left=last_seen+1，若该字符上次出现已在窗口外会让 left 后退。
• 只用集合记录出现过的字符，却不记录位置，无法直接跳过重复点之前的前缀。
• 并列时每次覆盖答案，导致返回最后一个最长子串而非约定的最早子串。
• 把题目中的 substring 误作可跳字符的 subsequence；窗口必须连续。

继续深挖

• 若字符集只包含 ASCII，可以用固定大小数组代替哈希表；Unicode 仍用映射更稳妥。
• 若流式输入只需长度，保留 left、位置计数与 last_seen；若还需完整子串，必须保留候选片段或可回读原流。
• 若要求大小写折叠或 Unicode 规范化，先约定转换后索引如何映射回原文。