387. 字符串中的第一个唯一字符
题目描述
输入一个字符串 s。找出在整个字符串里只出现过一次的字符中，位置最靠前的那个。
返回它的下标，下标从 0 开始。如果每个字符都至少出现两次，返回 -1。
示例 1
输入：s = "leetcode" 输出：0
解释：l 只出现一次，位于下标 0。
示例 2
输入：s = "loveleetcode" 输出：2
解释：l、o 都重复，v 是第一个只出现一次的字符，下标为 2。
示例 3
输入：s = "aabb" 输出：-1
解释：a 和 b 都出现两次。
数据范围
1 <= s.length <= 10^5s只含小写英文字母
解题思路：哈希表计数
一个字符是否唯一取决于整个字符串，扫描到它时还不知道后面会不会再出现。所以分两遍：第一遍用哈希表统计每个字符的出现次数；第二遍按原顺序找第一个次数为 1 的字符。
为什么正确
第二遍扫描到下标 i 时，s[0..i-1] 中的字符次数都大于 1，所以遇到的第一个次数为 1 的字符就是答案。
复杂度分析
时间 O(n)，空间 O(Σ)，Σ 为字符集大小（26）。
易错点
不能只扫一遍就判断“之前没见过”，那只说明它是第一次出现，后面还可能重复。必须先统计完整次数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def firstUniqChar(self, s: str) -> int:
cnt = collections.Counter(s)
for i, ch in enumerate(s):
if cnt[ch] == 1:
return i
return -1class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for (char ch : s.toCharArray()) cnt.merge(ch, 1, Integer::sum);
for (int i = 0; i < s.length(); i++) {
if (cnt.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> cnt;
for (char ch : s) cnt[ch]++;
for (int i = 0; i < (int)s.size(); i++) {
if (cnt[s[i]] == 1) {
return i;
}
}
return -1;
}
};func firstUniqChar(s string) int {
cnt := map[byte]int{}
for i := 0; i < len(s); i++ {
cnt[s[i]]++
}
for i := 0; i < len(s); i++ {
if cnt[s[i]] == 1 {
return i
}
}
return -1
}var firstUniqChar = function(s) {
const cnt = new Map();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
for (let i = 0; i < s.length; i++) {
if (cnt.get(s[i]) === 1) {
return i;
}
}
return -1;
};function firstUniqChar(s: string): number {
const cnt = new Map<string, number>();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
for (let i = 0; i < s.length; i++) {
if (cnt.get(s[i]) === 1) {
return i;
}
}
return -1;
}其他解法
三种方法都是 O(n)：计数法最简单，需要扫字符串两遍；存储下标把第二遍缩到字符集大小；队列法只扫一遍，并能在线回答。
解法 2：哈希表存储下标 时间 O(n)，空间 O(Σ)
遍历字符串，哈希表记录每个字符第一次出现的下标；字符再次出现时把值改成 -1。遍历结束后，在哈希表中找出所有不为 -1 的值里最小的那个。没有这样的值就返回 -1。
第二次遍历只扫哈希表，规模是字符集大小 Σ 而不是 n，字符串很长时更快。代码比计数略复杂。
class Solution:
def firstUniqChar(self, s: str) -> int:
pos = {}
for i, ch in enumerate(s):
if ch in pos:
pos[ch] = -1
else:
pos[ch] = i
ans = len(s)
for p in pos.values():
if p != -1 and p < ans:
ans = p
return -1 if ans == len(s) else ansclass Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> pos = new HashMap<>();
int n = s.length();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pos.containsKey(ch)) pos.put(ch, -1);
else pos.put(ch, i);
}
int ans = n;
for (int p : pos.values())
if (p != -1 && p < ans) ans = p;
return ans == n ? -1 : ans;
}
}class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> pos;
int n = s.size();
for (int i = 0; i < n; i++) {
if (pos.count(s[i])) pos[s[i]] = -1;
else pos[s[i]] = i;
}
int ans = n;
for (auto& [ch, p] : pos)
if (p != -1 && p < ans) ans = p;
return ans == n ? -1 : ans;
}
};func firstUniqChar(s string) int {
pos := map[byte]int{}
n := len(s)
for i := 0; i < n; i++ {
if _, ok := pos[s[i]]; ok {
pos[s[i]] = -1
} else {
pos[s[i]] = i
}
}
ans := n
for _, p := range pos {
if p != -1 && p < ans {
ans = p
}
}
if ans == n {
return -1
}
return ans
}var firstUniqChar = function(s) {
const pos = new Map();
const n = s.length;
for (let i = 0; i < n; i++) {
if (pos.has(s[i])) pos.set(s[i], -1);
else pos.set(s[i], i);
}
let ans = n;
for (const p of pos.values())
if (p !== -1 && p < ans) ans = p;
return ans === n ? -1 : ans;
};function firstUniqChar(s: string): number {
const pos = new Map<string, number>();
const n = s.length;
for (let i = 0; i < n; i++) {
if (pos.has(s[i])) pos.set(s[i], -1);
else pos.set(s[i], i);
}
let ans = n;
for (const p of pos.values())
if (p !== -1 && p < ans) ans = p;
return ans === n ? -1 : ans;
}解法 3：队列延迟删除 时间 O(n)，空间 O(Σ)
哈希表记录字符第一次出现的下标，重复出现时标记为 -1。第一次出现的字符和下标入队。每读入一个字符后，不断弹出队首中已被标记为 -1 的字符。遍历结束后队首就是第一个唯一字符，队列为空则返回 -1。
只需扫描字符串一次，并且在任意时刻都能给出当前前缀的答案，适合数据流场景。需要额外的队列，代码最长。
from collections import deque
class Solution:
def firstUniqChar(self, s: str) -> int:
pos = {}
q = deque()
for i, ch in enumerate(s):
if ch not in pos:
pos[ch] = i
q.append((ch, i))
else:
pos[ch] = -1
while q and pos[q[0][0]] == -1:
q.popleft()
return q[0][1] if q else -1class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> pos = new HashMap<>();
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!pos.containsKey(ch)) {
pos.put(ch, i);
q.offerLast(new int[]{ch, i});
} else {
pos.put(ch, -1);
while (!q.isEmpty() && pos.get((char) q.peekFirst()[0]) == -1) q.pollFirst();
}
}
return q.isEmpty() ? -1 : q.peekFirst()[1];
}
}class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> pos;
queue<pair<char, int>> q;
for (int i = 0; i < (int)s.size(); i++) {
char ch = s[i];
if (!pos.count(ch)) {
pos[ch] = i;
q.emplace(ch, i);
} else {
pos[ch] = -1;
while (!q.empty() && pos[q.front().first] == -1) q.pop();
}
}
return q.empty() ? -1 : q.front().second;
}
};func firstUniqChar(s string) int {
pos := map[byte]int{}
q := []int{}
for i := 0; i < len(s); i++ {
ch := s[i]
if _, ok := pos[ch]; !ok {
pos[ch] = i
q = append(q, i)
} else {
pos[ch] = -1
for len(q) > 0 && pos[s[q[0]]] == -1 {
q = q[1:]
}
}
}
if len(q) == 0 {
return -1
}
return q[0]
}var firstUniqChar = function(s) {
const pos = new Map();
const q = [];
let head = 0;
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (!pos.has(ch)) {
pos.set(ch, i);
q.push(i);
} else {
pos.set(ch, -1);
while (head < q.length && pos.get(s[q[head]]) === -1) head++;
}
}
return head < q.length ? q[head] : -1;
};function firstUniqChar(s: string): number {
const pos = new Map<string, number>();
const q: number[] = [];
let head = 0;
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (!pos.has(ch)) {
pos.set(ch, i);
q.push(i);
} else {
pos.set(ch, -1);
while (head < q.length && pos.get(s[q[head]]) === -1) head++;
}
}
return head < q.length ? q[head] : -1;
}