Learning Outcome
After this lesson, you should be able to count characters first and then preserve order with a second pass.
Problem Statement
Given a string, return the index of its first non-repeating character, or -1 if none exists.
| Input | Output | Why |
|---|---|---|
s = "leetcode" | 0 | The character l appears once and is the first unique character. |
Brute Force Approach
For each character, scan the entire string to count it. This repeats work.
Optimized Approach
Build a frequency table once. Then scan the string in original order and return the first index with frequency 1.
Exact Pseudocode
freq = character counts
for i from 0 to length(s) - 1:
if freq[s[i]] == 1:
return i
return -1Reference Code
class Solution:
def firstUniqChar(self, s):
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1Sample Dry Run
| Step | State | Result |
|---|---|---|
| Count | l:1, e:3, t:1, c:1, o:1, d:1 | Frequency table ready |
| Index 0 | l has count 1 | Return 0 |
| No need | Later unique chars exist | First unique is already found |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | The string is scanned twice. |
| Space | O(1) | For lowercase English letters, the frequency array has fixed size. |
Edge Cases
- If no unique character exists, return -1.
- Return the first unique by original index, not by map order.
- If the character set is larger, use a hashmap instead of size 26.
Interview Checklist
- Count first, then scan in original order.
- Do not return the first map key with count 1.
- Match the frequency structure to the character set.
FAQs
Why two passes?
The first pass learns all counts. The second pass preserves the original order.
Why not sort the string?
Sorting loses the original index order required by the problem.
What is the core pattern?
Frequency map plus order-preserving scan.