First Unique Character in a String
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
s = "leetcode"0The 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
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. This two-pass approach reduces the time complexity to O(n).
Optimal Approach
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.
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
| 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 |
Step-by-Step Solution
Count Frequencies of All Characters in the String
| 4 | count = {} |
| 6 | for 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
| 9 | for i in range(len(s)): |
| 10 | if count[s[i]] == 1: |
| 11 | return i |
| 13 | return -1 |
Objective
To scan the string and find the earliest character whose frequency is exactly one.
Key Insight
By leveraging the precomputed frequency map, the algorithm can quickly check each character's count in order, returning the first index where the count is one. This avoids redundant counting and ensures the earliest unique character is found efficiently.
Interview Quick-Check
Core Logic
Iterate over the string and use the frequency map to identify the first character with count one.
State & Boundaries
Return -1 if no unique character exists, ensuring correct handling of edge cases.
Common Pitfalls & Bugs
Failing to return immediately upon finding the first unique character can lead to incorrect results or unnecessary computation.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
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.
for c in s:Iterate over each character in the string.
This loop performs a single pass to gather frequency information for all characters.
count[c] = count.get(c, 0) + 1Increment the count for the current character in the frequency map.
Updating counts in the hash map accumulates the total occurrences of each character efficiently.
for i in range(len(s)):Iterate over the string indices to check character frequencies in order.
This loop ensures the earliest unique character is found by scanning from left to right.
if count[s[i]] == 1:Check if the current character's frequency is exactly one.
This condition identifies unique characters, which are candidates for the answer.
return iReturn the index of the first unique character found.
Returning immediately upon finding the first unique character guarantees the earliest index is returned.
return -1Return -1 if no unique character exists in the string.
This return value correctly signals that the string contains no non-repeating characters.
Test Your Understanding
Why is it necessary to perform two passes over the string instead of just one?
Because the frequency of each character must be known before determining which character is unique and appears first. The first pass collects counts, and the second pass uses these counts to identify the earliest unique character.
Related Problems
Hash Maps pattern
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