First Unique Character in a String: Frequency Counting

First Unique Character in a String is LeetCode 387, rated Easy. Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example: s = "leetcode". The answer is 0 because 'l' is the first character that appears only once.

Example: s = "aabb". Every character repeats, so the answer is -1.

This problem is a direct application of the frequency counter pattern. If you have solved Valid Anagram or Ransom Note, you already know the core technique. The twist here is that you are not just comparing two frequency maps. Instead, you build one map, then scan the original string to find the first character whose count is exactly 1.

The key insight

You cannot determine whether a character is unique until you have seen the entire string. The character 'l' at index 0 might look unique early on, but you need to verify that it never appears again later. So the algorithm needs two passes: one to count everything, and one to check.

A hash map (or a fixed-size array of 26 entries for lowercase English letters) stores the count for each character. After building it, you walk the string a second time, and the first character with a count of 1 is your answer.

The approach

1. Create an empty hash map to store character frequencies.
2. Walk through every character in s and increment its count in the map.
3. Walk through s a second time. For each character, check if its count in the map is 1.
4. The first character with count 1 is your answer. Return its index.
5. If you finish the second pass without finding any count of 1, return -1.

The code

def first_uniq_char(s: str) -> int:
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

Complexity

Time: O(n). You make two passes through the string, each taking O(n). Two passes is still O(n).

Space: O(1). The frequency map holds at most 26 entries because the input is limited to lowercase English letters. A constant number of entries means constant space, regardless of how long the string is.

Building blocks

Frequency counting with hash maps

The frequency counter is one of the most reusable patterns in algorithm problems. You walk through a collection, and for each element you increment a count in a dictionary. The template looks like this:

freq = {}
for item in collection:
    freq[item] = freq.get(item, 0) + 1

This same template powers Valid Anagram (count characters, compare two maps), Ransom Note (count supply, verify demand), Group Anagrams (sorted string as a grouping key), and sliding window problems where you track character frequencies as elements enter and leave the window.

The difference in this problem is what you do after building the map. Instead of comparing two maps or checking a subset relationship, you scan the original string and use the map as a lookup. The order of the original string matters here, which is why you iterate over s in the second pass rather than iterating over the map keys.

Edge cases

• All characters are the same. A string like "aaaa" has no unique characters. Every count is greater than 1, so the second pass finds nothing and you return -1.
• Every character is unique. A string like "abcdef" means every count is 1. The second pass returns index 0 immediately.
• Single character string. s = "a" has one character with count 1. Return 0. The algorithm handles this naturally.
• The unique character is at the end. A string like "aabbc" has 'c' as the only unique character, at index 4. The second pass must walk the entire string before finding it.

From understanding to recall

This problem is easy to understand, but that does not mean the pattern will stick. The frequency counter plus a second scan is a two-step recipe, and you need both steps to fire automatically when you see similar problems. Three weeks from now, when you encounter a problem that asks "find the first element satisfying some frequency condition," you want the two-pass structure to come to mind immediately.

Spaced repetition helps lock this in. You practice building the frequency map and writing the second-pass scan from scratch, at increasing intervals. After a few cycles, the code is in your hands, not just in your memory.

Related posts

• Valid Anagram - The classic frequency counter problem where you compare two strings by their character counts
• Ransom Note - A frequency counting variant where one string must be a subset of another
• Group Anagrams - Uses sorted character frequencies as hash map keys to group words together