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

类型：字符串

1. 字符串中的第一个唯一字符 💚
https://leetcode-cn.com/problems/first-unique-character-in-a-string/

❓ 找到字符串中第一个不重复的字符，返回其下标，不存在则返回 -1

💡 哈希存出现次数

第一次遍历，生成哈希表。字符为键，出现次数为值。

第二次遍历，返回第一个出现次数为 1 的字符。
```
class Solution:
    def firstUniqChar(self, s: str) -> int:
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return i
        return -1
```
时间复杂度：O(n)，空间复杂度：O(x)，x 指字符集大小，x ≤ 26

💡 哈希存储索引

我们可以在构建哈希表的时候，直接存储字符的下标。当重复出现的时候，我们直接在哈希表中将该字符的值改为 -1，这样我们在第二次遍历的时候就只需要遍历哈希表，找到下标不等于 -1 且最小的字符即可。
```
class Solution:
    def firstUniqChar(self, s: str) -> int:
        position = dict()
        n = len(s)
        for i, ch in enumerate(s):
            if ch in position:
                position[ch] = -1
            else:
                position[ch] = i
        first = n
        for pos in position.values():
            if pos != -1 and pos < first:
                first = pos
        if first == n:
            first = -1
        return first
```
时间复杂度：O(n)，空间复杂度：O(x)，x 指字符集大小，x ≤ 26

💡 队列 + 哈希

队列具有先进先出的性质，因此适合用来求这种「第一个」什么什么的问题。

其实跟方法二差不多，只不过通过队列，把对哈希表的遍历也免了。

具体地，当我们遍历到一个字符，若当前字符不在哈希表中，我们将其记录到哈希表，并将字符和下标构成二元组入队列尾。否则我们检查队列头部元素是否满足只出现一次，不满足的话将其弹出，务必保证头部元素只出现一次，此时我们就可以将当前数组和下标构成的二元组入队列尾了。当然，我们要同步更新哈希表。

这里，我们只维护队列头部元素符合只出现一次。这是一种「延时删除」技巧。因为，如果头部元素符合要求的话，我们最终取的也就是头部元素。后面的元素是否符合要求对我们没有影响。只有在头部元素发生了变化，我们才需要逐一检查，最终目的也只是保证新的头部元素符合要求即可。
```
class Solution:
    def firstUniqChar(self, s: str) -> int:
        position = dict()
        q = collections.deque()
        n = len(s)
        for i, ch in enumerate(s):
            if ch not in position:
                position[ch] = i
                q.append((s[i], i))
            else:
                position[ch] = -1
                while q and position[q[0][0]] == -1:
                    q.popleft()
        return -1 if not q else q[0][1]
```
时间复杂度：O(n)，空间复杂度：O(x)，x 指字符集大小，x ≤ 26