First Unique Character in a String
Problem statement
You get a string s. Find the first character in it that never repeats anywhere else in the string, and return that character's index. If every character repeats, return -1.
Think of it as scanning a log line or an identifier for the first "one-off" symbol — the first character that doesn't show up again anywhere else.
Examples
Example 1
Input: s = "leetcode"
Output: 0
Explanation: 'l' at index 0 never appears again later in the string, and no character before it could beat it to the title of "first," so it wins immediately.
Example 2
Input: s = "loveleetcode"
Output: 2
Explanation: 'l' (index 0) and 'o' (index 1) both repeat later in the string, so they're disqualified. 'v' at index 2 never appears again, so it's the first unique character.
Example 3
Input: s = "aabb"
Output: -1
Explanation: Every character in the string appears at least twice, so there's no unique character at all — the answer is -1.
Hints
Approach
Optimal: Count first, then scan
Intuition
The brute force is slow because it re-answers "how many times does this character appear?" from scratch for every single index, throwing away the counting work it already did. Instead, count every character's total frequency across the whole string just once, in a single pass. Then, in a second pass over the string in its original order, the first character whose total count is exactly 1 is the answer — because we're checking positions left to right, the first one found really is the first unique character.
This is what makes it faster than the brute force: the first pass replaces n separate O(n) counting scans with a single O(n) scan, and the second pass is a single O(n) lookup-and-check sweep.
Steps
- Build a count table (a fixed array of 26 for lowercase letters, or a hash map for a general alphabet).
- Walk the string once, incrementing the count for each character seen.
- Walk the string a second time, in order, and return the index of the first character whose count is exactly 1.
- If the second pass finishes with no match, return
-1.
Dry run
s = "loveleetcode"
Pass 1 — build counts:
| character | l | o | v | e | t | c | d |
|---|---|---|---|---|---|---|---|
| count | 2 | 2 | 1 | 4 | 1 | 1 | 1 |
Pass 2 — scan left to right for the first count of 1:
| i | s[i] | count[s[i]] | == 1? |
|---|---|---|---|
| 0 | l | 2 | no |
| 1 | o | 2 | no |
| 2 | v | 1 | yes → return 2 |
Edge cases: if every character repeats ("aabb"), pass 2 finishes without finding a count of 1, so the function falls through to -1. If the string has only one character, pass 1 gives it a count of 1, and pass 2 returns index 0 right away.
Complexity
Time O(n) - The string is walked exactly twice, back to back: once to build the count of every character, and once to find the first character whose count is 1.
Space O(1) - The input is limited to lowercase English letters, so the count table only ever needs 26 slots, no matter how long the input string is.
class Solution:
def firstUniqChar(self, s: str) -> int:
counts: dict[str, int] = {}
for ch in s:
counts[ch] = counts.get(ch, 0) + 1
for i, ch in enumerate(s):
if counts[ch] == 1:
return i
return -1
if __name__ == "__main__":
print(Solution().firstUniqChar("leetcode")) # 0
print(Solution().firstUniqChar("loveleetcode")) # 2
print(Solution().firstUniqChar("aabb")) # -1RecapThe whole problem in a few lines, for the night before
- Spot it: find the first character that appears only once
- Idea: pass 1 counts every character; pass 2 returns the first index whose count is 1
- Cost: O(n) time, O(1) space (26 letters)
- Trap: return the index, not the character, and return -1 when nothing is unique
Interview follow-ups
The string is a live stream and you can't store the whole thing. How would you find the first unique character so far, after each new character arrives?
Keep the same count map, updated as characters arrive, plus a queue (or ordered structure) of candidates that currently have a count of 1. After each new character, update its count and pop any candidates from the front of the queue whose count is no longer 1. The front of the queue is always the current answer. Each character is still processed in roughly constant amortized time, and memory only holds the counts and the candidate queue, not the whole stream.
What if you need the first character that repeats exactly twice, not the first unique one?
The approach barely changes: build the same count table in one pass, then scan again for the first index whose count equals exactly 2 instead of 1. Same O(n) time, same O(1) space — only the comparison value changes.
Frequently asked questions
Counting on the fly (the brute force) answers the same question — "how many times does this character appear?" — from scratch for every index, so the same characters get re-counted over and over. Splitting the work into two clean passes means every character is only ever counted once, and the second pass only ever does one lookup per position instead of a whole re-scan.
The count table's size depends on how many distinct characters can appear, not on the length of the string. Since the problem restricts s to lowercase English letters, the table never needs more than 26 slots, no matter whether the string is 5 characters or 100,000. That's what makes it constant space rather than space that grows with the input.
A fixed 26-slot array no longer works, since the alphabet isn't bounded the same way. Swap it for a hash map keyed by character; the algorithm and both passes stay identical, just with O(k) space for k distinct characters instead of a flat O(1).
It's a clean test of the "count first, then look up" pattern, which comes up constantly when scanning logs or config values for the first entry that's genuinely unusual — the first status code, error type, or hostname that shows up exactly once, as opposed to ones that repeat across many lines.