First Unique Character in a String
First Unique Character in a String: return the index of the first character that appears exactly once, or -1 if every character repeats.
- 1 <= s.length <= 10⁵
- s consists of only lowercase English letters
Intuition
Uniqueness is a property of the whole string, so it cannot be decided while first reading a character — a later duplicate may still appear. That forces two passes: count every character, then walk the string again in order and return the first index whose count is 1. The second pass must follow the original order, because the answer is the first such character, not any of them.
Any question asking for the first or last element with a global property needs the property computed first and the order applied second. The tell is that a decision at index i depends on data after i. Find the Difference and Sort Characters By Frequency share the counting step.
Approach
Before reading on: explain why the answer cannot be decided during a single left-to-right pass. Then work out why the second pass must walk the string rather than the frequency map.
Why one pass cannot work
At the moment you read index 0 you cannot know whether that character recurs at index 500. Any single-pass attempt must therefore either look ahead — which is the quadratic scan in disguise — or defer the decision. Counting first resolves this: after the counting pass every character's total is final, so the second pass can decide each index in constant time. The two passes together are still O(n), which is why this beats the nested search.
Counting, then scanning in order
Build a frequency map of all characters in one pass. Then iterate the string by index and return the first i where count[s[i]] == 1. Iterating the map instead of the string is a subtle error: dictionaries preserve insertion order in modern Python, which makes it appear to work, but the value needed is the index, and recovering it with s.index(ch) adds a linear search per candidate. Scanning the string directly gives the index for free and keeps the pass linear.
Bounding the space by the alphabet
The constraints say the string is lowercase English letters, so the map holds at most 26 entries regardless of input length — making the space O(1) rather than O(n). A fixed 26-slot array indexed by ord(c) - ord('a') makes that explicit and is what the C++ and Java versions use; it also avoids hashing entirely, so lookups are a single array access. Time is O(n) for the two passes, with the second usually stopping early.
Solution & live demo
Common pitfalls
Searching for each character's other occurrence
for i, ch in enumerate(s):
if ch not in s[i+1:] and ch not in s[:i]:
return icounts = Counter(s)
for i, ch in enumerate(s):
if counts[ch] == 1:
return iEach slice copies part of the string and scans it, giving O(n²) time and O(n) extra memory per iteration. On a 10⁵-character input this times out.
Iterating the frequency map instead of the string
for ch, n in counts.items():
if n == 1:
return s.index(ch)for i, ch in enumerate(s):
if counts[ch] == 1:
return iThis relies on dictionary insertion order to be correct at all, and s.index performs a fresh linear search for every candidate. Scanning the string yields the index directly.
Returning the character rather than its index
return ch
return i
The problem asks for the position. Returning the character itself type-checks in Python and fails silently against the expected output.
Edge cases
No count equals 1, so the loop finishes and -1 is returned.
Its count is 1, so index 0 is the answer.
The scan runs the full length before finding it.
The scan returns 0 immediately on the second pass.
Index 0 qualifies, so the scan stops at once.