How can I solve the 'First Unique Character in a String' problem using a queue?

You can solve this problem using a hash table to track character frequencies and a queue to maintain the order of characters, ensuring the first unique character is found efficiently.

What is the time complexity of the 'First Unique Character in a String' problem?

The time complexity is O(N), where N is the length of the string, as we process each character once.

Are there any edge cases to consider in this problem?

Yes, you should account for strings where all characters are repeating or where the string contains only one character.

What if the string contains uppercase letters or other symbols?

The current solution assumes only lowercase English letters, but the approach can be adapted to handle uppercase letters and other characters with slight modifications.

How does GhostInterview help me with this problem?

GhostInterview provides a structured approach and helps you stay on track with efficient algorithms, avoiding common pitfalls in string and queue-based problems.

#387

Easy

auto_awesome队列·driven·状态·processing

LeetCode 题解工作台

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

给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。示例 1：输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 提示: 1 …

哈希表字符串队列计数

题目描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

1 <= s.length <= 10⁵
s 只包含小写字母

lightbulb

解题思路

方法一：计数

我们用一个哈希表或者一个长度为 $26$ 的数组 $\text{cnt}$ 来存储每个字符出现的次数，然后从头开始遍历每个字符 $\text{s[i]}$ ，如果 $\text{cnt[s[i]]}$ 为 $1$ ，则返回 $i$ 。

遍历结束后，如果没有找到符合条件的字符，返回 $-1$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集，本题中字符集为小写字母，所以 $|\Sigma|=26$ 。

1

2

3

4

5

6

7

8

class Solution:
    def firstUniqChar(self, s: str) -> int:
        cnt = Counter(s)
        for i, c in enumerate(s):
            if cnt[c] == 1:
                return i
        return -1

speed

复杂度分析

指标	值
时间	\mathcal{O}(N)
空间	\mathcal{O}(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate effectively demonstrates the ability to use a hash table for frequency counting.
question_mark
Candidate efficiently handles the queue to maintain order for character processing.
question_mark
Candidate avoids unnecessary computations and keeps the algorithm within the required time and space complexity.

warning

常见陷阱

外企场景

error
Misusing a stack instead of a queue, which may lead to incorrect order processing of characters.
error
Not handling edge cases, like strings with all repeating characters.
error
Overcomplicating the solution, such as by using nested loops or unnecessary data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string contains uppercase letters?
arrow_right_alt
What if we need to find the second unique character instead?
arrow_right_alt
What if the string is very large, and performance optimization is required?

help

常见问题

外企场景

继续练习

#451 根据字符出现频率排序 #692 前K个高频单词 #767 重构字符串