DSA First Unique Character

The problem

A unique character in a string is a character that appears exactly once. The task is to find the first such character. The answer is its index, not the character itself.

Some strings have no unique character at all. The answer for those strings is -1. The first character of the string is not automatically the answer, because it may appear again later.

cases = [
    ("leetcode", 0),
    ("loveleetcode", 2),
    ("aabb", -1),
    ("aabbcdd", 4),
]
for s, expected in cases:
    print(repr(s), "first unique index:", expected)

Read the second row carefully. In loveleetcode, the letter l appears twice and o appears twice. The letter v at index 2 is the first character that appears only once.

Intuition

The first idea is to take the characters in order and ask about each one. Does this character appear anywhere else in the string? The first character with a no answer wins.

That question is the right question. The problem is its price. Answering it for one character means scanning the rest of the string, and the scan restarts for every character.

s = "aabbcdd"
first = s[0]
print("first character:", repr(first))
print("appears again later:", first in s[1:])
print("its total count:", s.count(first))

The letter a opens the string and still fails the test. Position alone proves nothing. Only a count over the whole string can say whether a character is unique, and that observation points at the fix: count everything once, before judging any character.

Brute force: recount for every character

The straightforward method follows the first idea literally. For each index, it counts how many times that character occurs in the whole string. The first index whose count is exactly one is the answer.

def first_unique_brute(s):
    comparisons = 0
    for i in range(len(s)):
        count = 0
        for j in range(len(s)):
            comparisons += 1
            if s[j] == s[i]:
                count += 1
        if count == 1:
            return i, comparisons
    return -1, comparisons

for s in ["aabbc", "aabb"]:
    idx, comparisons = first_unique_brute(s)
    print(repr(s), "-> index", idx, "comparisons:", comparisons)

The method finds the right answers. It also repeats the same counting work constantly. The count of a at index 0 and the count of a at index 1 are the same question asked twice, and the method pays for both.

The optimal solution: count once, then scan

A first pass counts every character in the whole string, and a second pass returns the first index whose stored count is one. Two passes replace the repeated recounting.

The order of the passes matters. The count pass must finish before the scan starts, because a character early in the string can be disqualified by a repeat near the end. The scan then walks in string order, so the first count of one it meets is the answer.

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

cases = [
    ("leetcode", 0),
    ("loveleetcode", 2),
    ("aabb", -1),
    ("aabbcdd", 4),
]
for s, expected in cases:
    print(repr(s), "->", first_unique(s), "expected", expected)

All four cases from the start of the article pass. The table is keyed by character, and the scan is driven by position. That split is what lets the answer be an index even though the counting never tracks positions.

Walkthrough

Follow the string aabbc. Its unique character is c, at the very end. The walkthrough shows the finished count table first, then the scan that reads it.

s = "aabbc"
counts = {}
for ch in s:
    counts[ch] = counts.get(ch, 0) + 1
print("counts:", list(counts.items()))
for i, ch in enumerate(s):
    print("index", i, "char", repr(ch), "count", counts[ch], "->", "answer" if counts[ch] == 1 else "skip")
    if counts[ch] == 1:
        break

The counts show a and b at two each, and c at one. The scan checks index 0 and reads the count of a, which is 2. It skips ahead. Indexes 1, 2 and 3 also read counts of 2.

Index 4 reads a count of 1. The scan stops there. That index is the answer, and no later character can change it, because the scan moves in order.

Complexity

The two-pass solution takes O(n) time, where n is the length of the string: one pass to count and one pass to scan. It takes O(k) space, where k is the number of distinct characters, because the table holds one entry per distinct character.

def brute_comparisons(s):
    comparisons = 0
    for i in range(len(s)):
        count = 0
        for j in range(len(s)):
            comparisons += 1
            if s[j] == s[i]:
                count += 1
        if count == 1:
            return comparisons
    return comparisons

def two_pass_steps(s):
    steps = 0
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
        steps += 1
    for ch in s:
        steps += 1
        if counts[ch] == 1:
            break
    return steps

for n in [8, 16, 32]:
    s = "abcd" * (n // 4)
    print("length", n, "brute comparisons:", brute_comparisons(s), "two-pass steps:", two_pass_steps(s))

The test strings repeat abcd, so no character is unique and both methods scan everything. The brute-force comparisons are the length squared. The two-pass steps are twice the length. Doubling the string quadruples one count and only doubles the other.

Edge cases and pitfalls

An empty string has no characters to scan. The count table is empty, the scan runs zero times, and the function falls through to -1. No special case is needed, as long as the code does not assume a first character exists.

Returning the character instead of its index is the classic slip. The problem asks for a position. The scan uses enumerate for exactly this reason: it carries the index alongside the character.

A subtler slip is hunting for a count of one in table order rather than string order. The contract is about position in the string. Scanning the string itself keeps that contract obvious.

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

for s in ["", "x", "zzzz", "aabbccd", "abac", "aA"]:
    print(repr(s), "->", first_unique(s))

A single character is unique by definition, so its index is 0. A unique character can sit at the very last index, as d does in aabbccd. The pair aA answers 0, because case makes the two characters distinct and both are unique.