First Unique Character in a String (LeetCode 387)

The problem

You get a string s of lowercase letters. Return the index of the first character that appears exactly once in the whole string. If there is no such character, return -1.

Input:  "loveleetcode"
Output: 2

l and o both appear twice, so they don’t count. v at index 2 appears only once, and it’s the first such character.

How to think about it

Start with brute force. For each index i, scan the whole string to see whether s[i] appears anywhere else. The first one that doesn’t is the answer. That is O(n²).

Why one pass isn’t enough. When you’re standing on a character, you can’t know whether it’s unique yet, because a copy might appear later. “Unique” is a property of the whole string, so you need to have seen everything before deciding.

The key insight: two passes, count first, decide second. Pass one counts every character with a hash map. Pass two walks the string in its original order and returns the first index whose character has count 1. Walking the string again (rather than the map) is what guarantees you get the first unique character.

Which pattern is this? Hash map frequency counting, followed by an ordered scan. The tell is “first element with some frequency property”.

Approach

1. Count every character of s into cnt.
2. Walk s from left to right with index i.
3. Return i as soon as cnt[s[i]] == 1.
4. If the walk ends, no character is unique; return -1.

Solution

from collections import Counter

def first_uniq_char(s):
    cnt = Counter(s)                       # pass 1: frequency of each character
    for i, c in enumerate(s):              # pass 2: original order
        if cnt[c] == 1: return i
    return -1
# first_uniq_char("loveleetcode") -> 2

Dry run

On "loveleetcode", pass one gives {e: 4, l: 2, o: 2, v: 1, t: 1, c: 1, d: 1}. Pass two:

On "aabb" every count is 2, so the scan finishes and returns -1.

Complexity

• Time: O(n). Two linear passes over the string.
• Space: O(1). At most 26 keys for lowercase letters (O(k) for an alphabet of size k).

Edge cases and pitfalls

• No unique character ("aabb"): return -1, not None.
• Single character: "z" returns 0.
• Scanning the dictionary instead of the string: dictionaries keep insertion order in Python 3.7+, so it happens to work, but it returns the character, not the index, and it relies on a detail. Scan the string.
• Returning the character instead of the index is a common misread of the problem.
• Streaming follow-up: if characters arrive one by one, keep counts plus an ordered structure (a queue or an OrderedDict) of candidates, and drop from the front any that have become repeats.

Related problems

• Valid Anagram (LeetCode 242): character counts compared across two strings.
• Ransom Note (LeetCode 383): character counts as a supply-and-demand check.
• Sort Characters By Frequency (LeetCode 451): count, then order the characters by count.