Amazon OA：字符串第一个不重复字符，计数与在线追问

题意与假设

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

• 训练合同返回Python Unicode code point索引；无解-1，不是UTF-8字节偏移。
• 大小写和空白均是不同或有效字符，不做隐式规范化；若产品按可见字形计数须另定分词。

解题路线

1. 第一遍Counter统计全串出现次数，第二遍从头找count=1的字符；频表只负责唯一性，原串负责“第一个”。
2. 正确性：全部出现次数在第二遍前已固定；每个更早位置都被证明不唯一，故第一次命中的位置就是答案。不能在第一遍看到一次就立即返回，后面可能重复。
3. 流式接口可维持计数和按首次出现排序的候选队列，重复字符从队头惰性淘汰。每次append后的答案只对当前前缀成立；若允许删除或滑动窗口，计数由2降到1时还需恢复有序候选。
4. 面试先问返回字符还是位置；编码规范化、case-fold可能改变长度和索引，要保留规范化位置到原位置的映射。

手动走一遍

训练例aabbcdcdx返回8；abac返回1；空串返回-1。前缀ab的答案a，追加a后改为b，说明在线答案可变化。

Python 参考实现

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

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

from collections import Counter


def first_unique(text):
    """Return first unique code-point index, or -1."""
    counts = Counter(text)
    return next((i for i, ch in enumerate(text) if counts[ch] == 1), -1)

复杂度

时间O(n)，空间O(u)，u为不同字符数；固定小字母表可用数组但不得假定题目限制。

易错点与追问

容易失分的边界

• 只遍历字典就依赖插入顺序与语言细节。
• 把code point索引当字节索引。
• 第一遍提前返回。

继续深挖

• 无解返回空值还是-1？
• 不断追加字符时如何查询？
• 窗口移出字符后唯一性如何恢复？