First Non-Repeating Character

First Non-Repeating Character is a classic string warm-up. It looks like it needs clever bookkeeping, but the winning move is the same one behind so many string problems: count everything first with a hash map, then make a decision in a second pass.

The slow way first

The obvious idea: for each character, scan the rest of the string to see if it appears again. The first character with no second appearance wins. That works, but every character triggers another full scan, so it is O(n²) — too slow for a long string.

The question to ask: what do I keep re-computing? I keep counting how often each character appears. If I counted once up front and stored the totals, the second scan would be trivial.

The idea: count once, then sweep

Make two passes. Pass 1 walks the string and tallies each character into a frequency map (count[ch]). Pass 2 walks the string again from the left and returns the first index whose character has a count of exactly 1. Because pass 2 goes left to right, the first match is guaranteed to be the earliest non-repeating character.

The key insight: counting is order-independent, but the answer depends on order. So we separate the two concerns — count in any order, then sweep left to right to honor positions.

Walk through it

Step through the animation. Pass 1 lights up the string and fills the count map underneath: m ends at 3, i at 2, n at 1, and u at 1. In pass 2 the pointer i scans from the left: m has count 3 and i has count 2, so we skip them. When i reaches n at index 2, its count is 1 — we stop and return 2. Notice u is unique too, but it sits later, so n wins.

Pseudocode

make an empty map called "count"        # maps a character -> how many times it appears
for each character ch in s:             # pass 1: tally everything
    count[ch] = count[ch] + 1
for each index i with character ch in s:  # pass 2: left to right
    if count[ch] is 1:
        return i                        # first unique character
return -1                               # none were unique

The Python solution

def first_uniq_char(s):
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1

• count is a dictionary mapping each character → how many times it appears.
• Pass 1 (for ch in s) tallies every character. count.get(ch, 0) returns 0 the first time we see a character, so the increment always works.
• Pass 2 (enumerate(s)) walks left to right, giving us both the index i and the character ch.
• Line 6 is the decision: count[ch] == 1 means this character appears exactly once.
• We return i on the first match, so the earliest unique character wins. If the loop finishes, every character repeated, so we return -1.

Complexity

We make two linear passes, so the time is O(n). The space is O(k), where k is the number of distinct characters — for lowercase letters that is at most 26, effectively constant. That trade — count with a hash map, then decide — generalizes to a huge family of frequency problems.

When this pattern shows up

Practice