387. First Unique Character in a String

Reformulated question¶

Given a lowercase string s, return the index of its first character that appears exactly once, or -1 if none exists.

Example:
s="loveleetcode" -> 2
counts: l:2, o:2, v:1, e:4, t:1, c:1, d:1
first count 1 is 'v' at index 2

Key trick¶

Count frequencies first, then scan left to right and return the first index whose count is 1.

Trap¶

Returning the first character seen once so far while scanning the first time.
Forgetting the answer is the first unique by index, not any unique character.
Overcomplicating it when the alphabet is only lowercase letters.

Why is this question interesting?¶

It tests a common pattern:

two-pass counting
preserving original order while using frequency data
choosing the simplest linear-time solution

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("leetcode", 0),
        ("loveleetcode", 2),
        ("aabb", -1),
        ("z", 0),
        ("aa", -1),
        ("ab", 0),
        ("aab", 2),
        ("abacabad", 3),
        ("dddccdbba", -1),
        ("xxyz", 2),
    ],
)
def test_firstUniqChar(s, expected):
    assert Solution().firstUniqChar(s) == expected

Solve the problem with idiomatic python¶

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Count each character.
        counts = {}
        for c in s:
            counts[c] = counts.get(c, 0) + 1

        # First index whose character appears once.
        for i, c in enumerate(s):
            if counts[c] == 1:
                return i

        return -1

Time: \(O(n)\)
Space: \(O(1)\) if treating the alphabet size as constant, else \(O(k)\)

A standard-library alternative:

from collections import Counter

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counts = Counter(s)
        for i, c in enumerate(s):
            if counts[c] == 1:
                return i
        return -1

Comment my solution¶

Your solution is correct and linear, but more complex than needed.

Good:
It keeps only current unique candidates.
It returns the minimum surviving index correctly.
Less good:
Using both a dict and a set is harder to read than simple counting.
The final minimum search is unnecessary if you just do a second pass on s.
if found == {} is less idiomatic than if not found.

A simpler version is easier to explain in interview:

first pass: count
second pass: first count 1

class Solution:
    def firstUniqChar(self, s: str) -> int:
        found = {}
        found_twice_or_more = set()

        for i, c in enumerate(s):
            if c in found_twice_or_more:
                continue
            if c in found:
                del(found[c])
                found_twice_or_more.add(c)
                continue
            found[c] = i

        if found == {}:
            return -1

        idx_min = len(s)
        for c, idx in found.items():
            if idx < idx_min:
                idx_min = idx
        return idx_min


## Test

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [("leetcode", 0), ("loveleetcode", 2), ("aabb", -1)]
)
def test_firstUniqChar(s, expected):
    assert Solution().firstUniqChar(s) == expected

Code¶

import pytest
from collections import Counter


class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Count each character.
        counts = {}
        for c in s:
            counts[c] = counts.get(c, 0) + 1

        # Return the first index whose character occurs once.
        for i, c in enumerate(s):
            if counts[c] == 1:
                return i

        return -1


class SolutionCounter:
    def firstUniqChar(self, s: str) -> int:
        # Same idea using the standard library.
        counts = Counter(s)
        for i, c in enumerate(s):
            if counts[c] == 1:
                return i
        return -1


@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("leetcode", 0),
        ("loveleetcode", 2),
        ("aabb", -1),
        ("z", 0),
        ("aa", -1),
        ("ab", 0),
        ("aab", 2),
        ("abacabad", 3),
        ("xxyz", 2),
    ],
)
def test_firstUniqChar(s, expected):
    assert Solution().firstUniqChar(s) == expected
    assert SolutionCounter().firstUniqChar(s) == expected

Solution().firstUniqChar("leetcode")      # 0
Solution().firstUniqChar("loveleetcode")  # 2
Solution().firstUniqChar("aabb")          # -1