How do you solve First Unique Character in a String?

Use a hash map to count frequencies in one pass over the string. Then iterate over the string again, returning the index of the first character with frequency one. If none exists, return -1. This approach is efficient and straightforward, with O(n) time and O(1) space since the character set is limited to lowercase English letters.

First Unique Character in a String

Q: What is the time complexity of First Unique Character in a String?

O(n). The algorithm makes two passes over the string of length n: one to count frequencies and one to find the first unique character. Each hash map operation is O(1) on average.

Q: What pattern does First Unique Character in a String use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When needing to identify unique or duplicate elements efficiently, use a hash map to count occurrences in one pass, then use a second pass to find the first element meeting the uniqueness criteria, enabling O(n) time complexity.

Easy Hash Maps

Problem

Given a string s, return the index of the first non-repeating character in it. If it does not exist, return -1.

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Example

Input: s = "leetcode"

Output: 0

The character 'l' appears only once and is the first such character in the string. The algorithm counts the frequency of each character: {'l':1, 'e':3, 't':1, 'c':1, 'o':1, 'd':1}. Then it scans the string from left to right, returning the index of the first character with count 1, which is index 0.

Approach

Straightforward Solution

A naive approach would check each character and scan the entire string to count its occurrences, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

The problem reduces to identifying the first character in the string whose frequency is exactly one. This requires counting occurrences and then scanning for the earliest unique character.

Path to Optimal

Preview

The key insight is to use a hash map (dictionary) to count the frequency of each character in a single pass, which takes O(n) time. Then, a second pass through the string checks the stored counts to find the first character with count one…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a hash map to count frequencies in one pass over the string. Then iterate over the string again, returning the index of the first character with frequency one…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes two passes over the string of length n: one to count frequencies and one to find the first unique character. Each hash map operation is O(1) on average.

Space

O(1)

The hash map stores counts for at most 26 lowercase English letters, which is constant space independent of input size.

Pattern Spotlight

Hash Maps (Frequency Counting)

When needing to identify unique or duplicate elements efficiently, use a hash map to count occurrences in one pass, then use a second pass to find the first element meeting the uniqueness criteria, enabling O(n) time complexity.

Solution

Python

1class Solution:
2    def firstUniqChar(self, s: str) -> int:
3
4        count = {}
5
6        for c in s:
7            count[c] = count.get(c, 0) + 1
8
9        for i in range(len(s)):
10            if count[s[i]] == 1:
11                return i
12
13        return -1

Step-by-Step Solution

Count Frequencies of All Characters in the String

4count = {}
6for c in s:
7    count[c] = count.get(c, 0) + 1

Objective

To build a frequency map that records how many times each character appears in the string.

Key Insight

Counting frequencies in a single pass allows the algorithm to gather all necessary information about character occurrences efficiently. Using a hash map keyed by characters provides O(1) average insertion and lookup, enabling a linear time solution.

Interview Quick-Check

Core Logic

Use a hash map to count each character's occurrences in one pass, enabling constant-time frequency lookups later.

Complexity

This step runs in O(n) time, where n is the length of the string.

Common Pitfalls & Bugs

Forgetting to initialize counts properly or using a data structure with slower lookups can degrade performance.

Identify and Return the Index of the First Unique Character

To scan the string and find the earliest character whose frequency is exactly one.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 4 Critical

count = {}

Initialize an empty dictionary to count character frequencies.

This dictionary serves as the frequency map, enabling O(1) average-time updates and lookups for each character.

Line 6 Critical

for c in s:

Iterate over each character in the string.

This loop performs a single pass to gather frequency information for all characters.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why is it necessary to perform two passes over the string instead of just one?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct First Unique Character in a String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the First Unique Character in a String drill

or drill a free problem

1	`class Solution:`
2	`def firstUniqChar(self, s: str) -> int:`
3
4	`count = {}`
5
6	`for c in s:`
7	`count[c] = count.get(c, 0) + 1`
8
9	`for i in range(len(s)):`
10	`if count[s[i]] == 1:`
11	`return i`
12
13	`return -1`