Finding the First Unique Character

Two passes. The first builds a frequency table for the whole string. The second walks the string from the left and returns the first character whose count is one. The order of the second pass is the whole point: the first unique character is defined by position, not by count.

from collections import Counter

def first_unique_char(text):
    counts = Counter(text)
    for char in text:
        if counts[char] == 1:
            return char
    return None

print(first_unique_char("leetcode"))
print(first_unique_char("aabb"))

The outputs are the letter l and None. In leetcode the characters l, e, t, c, o, d all appear twice except for u, which appears once, and u is the only unique character. In aabb every character appears twice, so there is no answer.

The mechanism is that counting alone cannot tell you which unique character comes first. The counter tells you the l in leetcode is unique only after you have seen the whole string. Scanning the original order afterwards gives you the position. Trying to return from inside the counting loop is a common mistake, because at that moment you do not yet know whether the character will repeat later.

The trade-off to name is space against time. The count table is O of k space where k is the number of distinct characters, and the whole algorithm is linear in the length of the string. The alternative is to scan once and keep the first candidate plus a flag marking it as suspect, which uses O of 1 space but is fiddly, because when a candidate is invalidated you have to remember the next one that was never a candidate at all. The two-pass version is worth the table in every realistic case.

Build the frequency table by hand with a dictionary, then scan the string again from the left and return the first character whose count is one.

def first_unique_char(text):
    counts = {}
    for char in text:
        counts[char] = counts.get(char, 0) + 1
    for char in text:
        if counts[char] == 1:
            return char
    return None

print(first_unique_char("leetcode"))
print(first_unique_char("aabb"))

The outputs are the letter l and None. The dictionary version behaves identically to the Counter version, because a Counter is a dictionary with a different default for missing keys.

The mechanism is the get call with a default of zero. It lets you read and increment a counter in one expression without checking whether the key exists first, which is what keeps the loop to a single statement. The alternative, using a membership test and then an assignment, is longer and slower because it hashes the key twice.

The trade-off to name is that a plain dictionary raises a key error when you read a missing key, while a Counter returns zero. That difference is the only functional distinction between the two, and it matters if you ever index the table for a key that was never inserted. In an interview, the plain dictionary version is the better one to write out, because it shows you understand what the library is doing rather than reaching for a helper, and it makes the two-pass structure obvious.

Keep a running count per character and remember the order in which characters arrived. When asked for the first unique character, walk that order and return the earliest character whose count is still one.

from collections import Counter


class UniqueCharacters:
    def __init__(self):
        self.counts = Counter()
        self.order = []

    def add(self, char):
        self.counts[char] += 1
        self.order.append(char)

    def first_unique(self):
        for char in self.order:
            if self.counts[char] == 1:
                return char
        return None


stream = UniqueCharacters()
for char in "leetcode":
    stream.add(char)
print(stream.first_unique())

The output is the letter l. In the stream l, e, t, c, o, d, e each arrive once, then e arrives again. The counts show that e now appears twice, and the order list shows that l is the earliest character whose count is still one.

The mechanism is the separation of two jobs. The count table answers how many times each character has arrived, and the order list answers when each character first arrived. The query then combines them: the earliest arrival with a count of one is the answer. Without the order list you would know which characters are unique but not which one comes first, and without the counts you would know the order but not whether a character has been repeated.

The trade-off to name is memory and query cost. The count table is O of k space for k distinct characters, and the order list grows with every character that arrives, so the space is O of n in the stream length rather than O of k. The query is a linear scan of the order list, which is acceptable if queries are rare. If the stream is long and queries are frequent, you would keep a queue of candidates and drop entries from the front as their counts rise above one, which gives constant amortised query cost at the price of a little more bookkeeping.