First Unique Character in a String

Intuition

Uniqueness is a global property: you cannot know a character is unique until you have seen the entire string. So make one pass to record the frequency of every character in a map, then make a second pass in the original order. The first position whose character has a recorded frequency of one is the answer, because scanning left to right guarantees you hit the earliest such index first.

Algorithm walkthrough

1. 1Initialize a frequency table for the characters.
2. 2Traverse the string once, incrementing the count for each character.
3. 3Traverse the string a second time from the start.
4. 4Return the index of the first character whose stored count equals one.
5. 5If the second pass finds none, return -1.

Implementation

class Solution:
    def firstUniqChar(self, s: str) -> int:
        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