Coding Interview PatternsFirst Unique Character in a String
EasyHash Maps
First Unique Character in a String
Explanation & Solution
Description
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Input: s = "leetcode"
Output: 0
Explanation: The character 'l' at index 0 is the first character that does not repeat.
Constraints
1 <= s.length <= 10⁵sconsists of only lowercase English letters
Approach
Hash Maps pattern
1. Count Character Frequencies
- Create a hash map
charCountto store the frequency of each character in the string - Iterate through the string and increment the count for each character
2. Find the First Unique Character
- Iterate through the string a second time, from left to right
- For each character, check its count in the hash map
- Return the index of the first character whose count is exactly
1
3. Handle No Unique Character
- If we finish scanning the entire string without finding a character with count
1, return-1
Key Insight
- Two passes through the string: the first builds the frequency map, and the second finds the earliest character with frequency 1
Time
O(n) where n is the length of the string (two linear passes)Space
O(1)the map holds at most 26 lowercase English lettersVisualization
Input:
[l, e, e, t, c, o, d, e]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps