First unique character

Lesson 3.5 · Easy · Counting · 6 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Find the index of the first letter that appears only once in the string.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

counta0

f10

f11

x12

g13

g14

h15

h16

i17

i18

Pass 1: count "a".

counts {a:1}

1 / 32

The idea

Complexity

Time	Space	Why
`O(n)`	`O(alphabet)`	One pass to count, one pass to find the first count of 1.

In Python

from collections import Counter
def first_unique(s):
    cnt = Counter(s)
    for i, ch in enumerate(s):
        if cnt[ch] == 1: return i
    return -1

Try it on LeetCode: First Unique Character in a String →

Summary: say it in the interview

First pass: count every letter. Second pass: return the first letter whose count is 1. Counting is the most common use of a hash map.
Time O(n), space O(alphabet). One pass to count, one pass to find the first count of 1.