#387

Easy

auto_awesomeQueue-driven state processing

LeetCode Problem Workspace

First Unique Character in a String

Find the index of the first non-repeating character in a string using efficient queue-driven state processing.

Problem Statement

Given a string s, your task is to find the index of the first non-repeating character in it. If no such character exists, return -1. A non-repeating character is one that does not appear in any other position within the string.

The solution should be efficient, ideally working in linear time relative to the length of the string. You may assume the string consists of lowercase English letters only and has a length between 1 and 105.

Examples

Example 1

Input: s = "leetcode"

Output: 0

The character 'l' at index 0 is the first character that does not occur at any other index.

Example 2

Input: s = "loveleetcode"

Output: 2

Example details omitted.

Example 3

Input: s = "aabb"

Output: -1

Example details omitted.

Constraints

1 <= s.length <= 105
s consists of only lowercase English letters.

Solution Approach

Hash Table for Frequency Counting

The first step is to count the frequency of each character in the string using a hash table. This helps quickly identify characters that appear more than once, allowing for faster processing.

Queue for Order Tracking

Use a queue to maintain the order of characters. As you iterate over the string, add characters to the queue and remove those that repeat. This ensures that the first character to remain in the queue is the first unique character.

Efficient Search

After building the frequency map and processing characters in the queue, the first character that remains in the queue is the unique character. The algorithm runs in linear time, O(N), making it optimal for large input sizes.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	\mathcal{O}(1)

The time complexity is O(N) since we traverse the string once and perform constant-time operations on the hash table and queue. The space complexity is O(1) because the hash table stores at most 26 characters (for lowercase English letters), which is a constant space requirement.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Counting

We use a hash table or an array of length $26$ $\text{cnt}$ to store the frequency of each character. Then, we traverse each character $\text{s[i]}$ from the beginning. If $\text{cnt[s[i]]}$ is $1$, we return $i$.

1

2

3

4

5

6

7

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

Continue Practicing

#451 sort characters by frequency #692 top k frequent words #767 reorganize string