字符串中的第一个唯一字符

题目描述
给定一个字符串 s，请你在该字符串中找到并返回第一个不重复（在整个字符串中只出现一次）的字符的索引。如果不存在这样的字符，则返回 -1。例如，对于 s = "leetcode"，第一个唯一字符是 'l'，索引为 0；对于 s = "loveleetcode"，第一个唯一字符是 'v'，索引为 2；对于 s = "aabb"，没有唯一字符，返回 -1。

解题过程

这道题的核心是统计每个字符的出现次数，然后按顺序找到第一个出现次数为 1 的字符。哈希表（或数组，因为字符集有限）是记录次数的理想工具。解题步骤如下：

步骤 1：遍历字符串，统计每个字符的出现次数

• 因为输入字符串只包含小写字母，但为了通用性，可以扩展为所有 ASCII 字符（包括大写、符号等）。这里假设字符集是 Unicode，适合用哈希表（字典）来记录，键是字符，值是出现次数。
• 遍历字符串 s 一次，对每个字符 c：
  • 如果 c 不在哈希表中，设置 count[c] = 1
  • 如果 c 已在哈希表中，将 count[c] += 1
• 时间复杂度 O(n)，n 是字符串长度。

示例：s = "loveleetcode"
遍历后得到哈希表（部分）：

'l': 2, 'o': 2, 'v': 1, 'e': 4, 't': 1, 'c': 1, 'd': 1

步骤 2：第二次遍历，找到第一个次数为 1 的字符

• 再次按顺序遍历字符串 s 的每个字符 c：
  • 查询哈希表中 c 的次数 count[c]
  • 如果 count[c] == 1，立即返回当前索引
• 如果遍历结束都没找到次数为 1 的字符，返回 -1
• 时间复杂度 O(n)，空间复杂度 O(字符集大小) 或 O(1) 如果字符集有限。

示例：s = "loveleetcode"

• 索引 0: 'l' → 次数 2，继续
• 索引 1: 'o' → 次数 2，继续
• 索引 2: 'v' → 次数 1，找到！返回索引 2

步骤 3：代码实现（Python示例）

def firstUniqChar(s: str) -> int:
    from collections import defaultdict
    count = defaultdict(int)
    
    # 第一次遍历，统计次数
    for c in s:
        count[c] += 1
    
    # 第二次遍历，找第一个次数为1的字符
    for i, c in enumerate(s):
        if count[c] == 1:
            return i
    
    return -1

步骤 4：优化与扩展

• 如果字符串很长但字符集很小，可以进一步优化空间，比如用固定大小的数组（如果字符是 ASCII 码，长度为 128 或 256 即可）。
• 另一种思路是使用哈希表记录每个字符的首次出现索引，如果再次出现则标记为 -1，最后遍历哈希表找最小非负索引。但需要遍历整个哈希表，在字符集大时可能效率略低，但仍是 O(n) 时间。

思考
这个题目是哈希表在频率统计和顺序查找中的经典应用，重点在于两次遍历分别完成统计和查找，保证顺序性。