First Unique Character in a String: Count, Then Scan Again

Problem

Given a string s, return the index of the first character that occurs exactly once in the whole string. If every character repeats, return -1. This is LeetCode 387, First Unique Character in a String.

The string has between 1 and about 10^5 characters, all lowercase English letters.

Examples

s = "racecars"     ->  3     ("e" is the only letter used once)
s = "stream"       ->  0     (every letter is unique, so the first one wins)
s = "abab"         ->  -1    (no unique letter)
s = "z"            ->  0

Approach 1: brute force

For each position, check whether its character appears anywhere else.

def first_unique_brute(s):
    for i, ch in enumerate(s):
        if all(s[j] != ch for j in range(len(s)) if j != i):
            return i
    return -1

Complexity: O(n²) time, O(1) extra space.

Approach 2: optimal (frequency count, two passes)

Key insight: “unique” is a property of the whole string, so you cannot decide it on the first visit. Count everything first, then make a second pass in the original order and pick the first character whose count is 1.

from collections import Counter

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

For a fixed lowercase alphabet, a list of 26 counters avoids hashing altogether:

def first_unique_array(s):
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Why it is correct: after the first pass, counts[ch] is the exact number of occurrences of ch in s. The second pass visits indices in increasing order and stops at the first one with count 1, which is the definition of the answer.

Complexity: O(n) time. Extra space is O(k) for an alphabet of size k: O(1) for 26 letters, and at most O(n) for arbitrary characters.

Tests

import random
import string

for f in (first_unique, first_unique_array, first_unique_brute):
    assert f("racecars") == 3
    assert f("stream") == 0               # all unique
    assert f("abab") == -1                # none unique
    assert f("z") == 0                    # single character
    assert f("aabbccd") == 6              # unique character at the end
    assert f("zzzz") == -1

assert first_unique("") == -1 and first_unique_brute("") == -1   # defensive

random.seed(2)
for _ in range(500):
    s = "".join(random.choice("abcde") for _ in range(random.randint(1, 12)))
    assert first_unique(s) == first_unique_array(s) == first_unique_brute(s)

Edge cases and pitfalls

• Return the index, not the character. Return -1, not None, when nothing qualifies.
• Do not try to decide in one pass by removing characters when you see them again: a character seen three times would be re-added on the third visit.
• If the input is not limited to lowercase letters, the 26-slot array breaks (negative or too-large indices); use Counter instead.
• Upper and lower case are different characters unless the problem says otherwise.

Where this shows up in data engineering

Counting then filtering for frequency 1 is GROUP BY key HAVING COUNT(*) = 1, used to find singleton keys such as customers with one order or events that never got a follow-up. Keeping the original order while doing it is what a window function like COUNT(*) OVER (PARTITION BY key) gives you in SQL.