014. First Unique Character

Why this mechanism works

A character that looks unique now may recur later. Finish counting before committing to the earliest index. The second pass retains input order, while the dictionary answers the global frequency question.

State and boundaries

counts is complete before selection. i is the next candidate index in original order.

Protocol

1. Count all characters.
2. Scan indices from the beginning.
3. Return the first index with count one.
4. Return -1 if none qualifies.

Visualization

leetcode
counts: l=1, e=3, t=1, c=1, o=1, d=1
scan from left -> index 0

Python implementation

def first_unique(text):
    counts = {}
    for char in text:
        counts[char] = counts.get(char, 0) + 1
    for i, char in enumerate(text):
        if counts[char] == 1:
            return i
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 first_unique: counts = {}
text='leetcode'; counts={}

L3 first_unique: for char in text:
text='leetcode'; counts={}; char='l'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1}; char='l'

L3 first_unique: for char in text:
text='leetcode'; counts={'l':1}; char='e'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1, 'e':1}; char='e'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1, 'e':2}; char='e'

L3 first_unique: for char in text:
text='leetcode'; counts={'l':1, 'e':2}; char='t'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1, 'e':2, 't':1}; char='t'

... 5 intermediate state changes omitted ...

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1, 'e':2, 't':1, 'c':1, 'o':1, ...}; char='d'

L3 first_unique: for char in text:
text='leetcode'; counts={'l':1, 'e':2, 't':1, 'c':1, 'o':1, ...}; char='e'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='leetcode'; counts={'l':1, 'e':3, 't':1, 'c':1, 'o':1, ...}; char='e'

L5 first_unique: for i, char in enumerate(text):
text='leetcode'; counts={'l':1, 'e':3, 't':1, 'c':1, 'o':1, ...}; char='l'; i=0

L2 first_unique: counts = {}
text='aabb'; counts={}

L3 first_unique: for char in text:
text='aabb'; counts={}; char='a'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='aabb'; counts={'a':1}; char='a'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='aabb'; counts={'a':2}; char='a'

L3 first_unique: for char in text:
text='aabb'; counts={'a':2}; char='b'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='aabb'; counts={'a':2, 'b':1}; char='b'

L4 first_unique: counts[char] = counts.get(char, 0) + 1
text='aabb'; counts={'a':2, 'b':2}; char='b'

L5 first_unique: for i, char in enumerate(text):
text='aabb'; counts={'a':2, 'b':2}; char='a'; i=0

L5 first_unique: for i, char in enumerate(text):
text='aabb'; counts={'a':2, 'b':2}; char='a'; i=1

L5 first_unique: for i, char in enumerate(text):
text='aabb'; counts={'a':2, 'b':2}; char='b'; i=2

L5 first_unique: for i, char in enumerate(text):
text='aabb'; counts={'a':2, 'b':2}; char='b'; i=3

Why the solution is correct

The counting pass determines final multiplicities. The selection pass tests candidates in increasing index order, so its first qualifying index is both globally unique and earliest. Exhaustion means every character is repeated.

Time and space

O(n) expected time and O(u) auxiliary space.

Common mistakes

Returning during the counting pass commits before future occurrences are known. Returning a dictionary key does not provide the requested index.

Reasoning card

Transfer exercise

Maintain the first unique character after every stream insertion; identify the extra order state a streaming solution needs.