First Unique Character in a String
给你一个由小写英文字母组成的字符串 s。找出整个字符串中第一个只出现一次的字符，并返回它的索引，从 0 开始计数。如果每个字符都出现了多次，则返回 -1。
函数
- sstring
- 要搜索的字符串，仅包含小写字母
- 返回值integer
- 第一个只出现一次的字母的索引；如果没有这样的字母，则返回 -1
约束条件
1 ≤ s.length ≤ 5 × 104s仅包含小写英文字母（a到z）。
示例
- 输入
- s = "coddycode"
- 输出
- 4
- 解释
- 在
coddycode中，c和o各出现两次，d出现三次。y（索引为 4）和e（索引为 8）都只出现一次，而且y排在前面，所以答案是 4。
- 输入
- s = "swiss"
- 输出
- 1
- 解释
- 字母
s出现了三次。索引 1 处的w和索引 2 处的i都出现了一次，而且w排在前面。
- 输入
- s = "aabbcc"
- 输出
- -1
- 解释
aabbcc中的每个字母都出现了两次，所以答案是-1。
进阶
字符会从数据流中逐个到达。每到达一个字符，你该如何报告目前为止第一个不重复的字符？
提示
逐个打开提示，每个都会多透露一点。
要判断一个字母是否只出现一次，你必须查看整个字符串，而不只是它前面的字母。
一共只有 26 个字母。如果你知道
s中每个字母出现了多少次，你能否在常数时间内回答任意位置的问题？分两次遍历。第一次，用一个包含 26 个计数器的数组统计每个字母。在第二次遍历中，从左向右遍历字符串，并返回第一个计数为 1 的字母的索引。如果遍历结束，返回
-1。
题解
当你看到某个字母时，它看起来可能是唯一的，但它也可能在字符串的最末尾再次出现，所以只从左到右看一遍是不够的。先统计每个字母出现的次数，然后在第二遍扫描时，就能用常数时间判断每个位置上的字母是否唯一。
查找每个字母的第二个副本
结果正确，但无法在最大的测试中运行完毕
思路
从左侧开始，对每个位置扫描整个字符串，查找是否有其他位置上的字母相同。两侧都要扫描：较早出现的副本和较晚出现的副本一样，都会使该字母不符合条件。第一个没有副本的位置就是答案。在 coddycode 中，位置 0 到 3 都能找到副本，而索引 4 处的 y 找不到副本。
如果每个字母都连续出现很长一段，遇到第一个副本就停止也没有帮助，例如先有 2000 个 a，再有 2000 个 b，依此类推：每次扫描都会经过前面所有连续段。当 n = 5 × 10^4 时，比较次数会超过 10 亿次。
算法
- 从左到右遍历每个索引
i： - 检查除
i之外的每个索引j，找到第一个满足s[j]等于s[i]的索引后停止。 - 如果没有这样的
j，则返回i。 - 如果每个索引都找到了一个相同的项，则返回
-1。
def firstUniqChar(s):
n = len(s)
for i in range(n):
repeated = False
for j in range(n): # look for another copy of s[i]
if j != i and s[j] == s[i]:
repeated = True
break
if not repeated:
return i
return -1统计字母，然后扫描
思路
对每个字母只计数一次，不要为每个位置重新搜索。字母只有 26 个，所以用 26 个计数器保存所有计数，并用字母的编码减去 a 的编码作为索引。
第一遍遍历会填充计数器；对于 coddycode，最后只有 y 和 e 的计数为 1。第二遍从左到右遍历字符串，并在遇到第一个计数为 1 的字母时停止，也就是索引为 4 的 y。两遍各遍历 n 步，时间复杂度为 O(n)；对于任意长度的字符串，26 个计数器占用的空间复杂度都是 O(1)。
算法
- 创建一个包含 26 个零的数组。
- 遍历
s中的每个字母，将其计数加 1。 - 从索引 0 开始再次遍历
s。返回第一个计数为 1 的字母对应的索引。 - 如果遍历结束，返回
-1。
def firstUniqChar(s):
counts = [0] * 26 # counts[0] is 'a', counts[25] is 'z'
for ch in s:
counts[ord(ch) - ord("a")] += 1
for i, ch in enumerate(s):
if counts[ord(ch) - ord("a")] == 1:
return i
return -1
易错点和边界情况
- 只检查位置
i之前的字母。在abca中，第一个a前面没有重复项，但它并不是唯一的。 - 第二次遍历时遍历计数器数组，而不是字符串。对于
ba，第一个值为 1 的计数器对应a，但答案是索引 0。 - 用字符的原始编码作为计数器的索引。
a的编码是 97，远远超出了 26 个计数器的范围。 - 返回字母而不是它的索引，或者在 Lua 或 R 中返回从 1 开始的索引。
常见问题3
字符串中第一个不重复字符的时间复杂度是多少？
统计字母，然后扫描字符串，需要经过两遍，每遍执行 n 步，因此时间复杂度为 O(n)。无论字符串长度是多少，26 个计数器占用的空间都相同，因此额外空间复杂度为 O(1)。
你能只遍历一次字符串就解决这个问题吗？
可以。遍历一遍字符串，为每个字母存储它首次出现的位置，或者在它再次出现时将其标记为重复。然后，在只出现过一次的 26 个字母中，取索引最小的那个。字符串只需读取一遍，最后检查需要 26 步。
应该使用哈希表还是数组来统计字母数量？
如果字符串只包含小写字母，使用包含 26 个计数器的数组会更小、更快。如果字符串可以包含任意字符，例如 Unicode 文本，那么哈希表是更合适的选择。算法保持不变：先计数，再扫描字符串。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def firstUniqChar(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "coddycode"
预期输出
4