Finding the First Unique Character in a String

Finding the First Unique Character in a String — From Brute Force to Blazing Fast

When working with strings, a common interview and real-world problem is: how do you find the first non-repeating character in a string? This article walks you through how to solve this efficiently—starting from the slowest brute-force way to the most optimal solution. You'll see the code, the logic, and learn how to think about such problems like a pro.

Problem Statement

Given a string s, return the index of the first character that doesn't repeat. If there's no such character, return -1.

Example Test Cases:

• Input: "leetcode" → Output: 0

• Input: "loveleetcode" → Output: 2

• Input: "a"*10**5 + "b" → Output: 100000

• Input: "aabbccdd..."*4000 + "z" → Output: 104000

• Input: "ab"*5*10**5 + "c" → Output: 1000000

Step 1 – Brute Force

This approach checks every character and counts how many times it appears. It's slow and doesn't scale for big strings.

# Brute-force solution
def first_unique_character(s: str):
    """
    Returns the index of the first character that appears only once.
    Time Complexity: O(n^2) because s.count(i) is O(n).
    """
    dp = {}
    for i in s:
        dp[i] = s.count(i)  # Very expensive for large strings
    
    for i in s:
        if dp[i] == 1:
            return s.index(i)
    return -1

print(f"Expected:0, Actual:", first_unique_character("leetcode"))
print(f"Expected:2, Actual:", first_unique_character("loveleetcode"))
print(f"Expected:100000, Actual:", first_unique_character("a"*10**5 + "b"))
print(f"Expected:104000, Actual:", first_unique_character("aabbccdd..."*4000 + "z"))
print(f"Expected:1000000, Actual:", first_unique_character("ab"*5*10**5 + "c"))

Why It's Bad

• Each call to s.count(i) scans the whole string.

• For large strings like 1 million characters, this is too slow.

Step 2 – The Optimal Way

We only scan the string twice — once to count, once to find the first unique.

# Optimal solution using hashmap
from typing import Optional

def first_unique_character(s: str) -> Optional[int]:
    """
    Return the index of the first non-repeating character.
    Time Complexity: O(n), Space Complexity: O(1) (since alphabet size is fixed).
    """
    count = {}

    # First pass: count frequency
    for idx, char in enumerate(s):
        count[char] = count.get(char, 0) + 1

    # Second pass: find the first char with count 1
    for idx, char in enumerate(s):
        if count[char] == 1:
            return idx
    return -1

Why It's Fast

• Only two passes through the string → O(n).

• Uses a hashmap to count frequencies efficiently.

Breaking It Down Like You’re 2 Years Old

1. Look at each letter and keep track of how many times each one shows up.

2. Go through the string again from the beginning.

3. The first letter that only shows up one time — we remember where it was!

Key Takeaways

1. What key data structure or trick did the optimal solution use?

• A hashmap (dictionary) to count how many times each character appears.

2. What pattern does it use?

• Counting Frequency + Index Scan.

• Classic HashMap-based pattern seen in character and array counting problems.

3. How could I recognize this pattern in a new problem?

• If the question asks to "find the first unique/repeating..." element, think: count first, then filter.

4. How could I come up with this solution on my own?

• Ask yourself: “Can I separate the count phase from the selection phase?”

• Then use a dictionary to store frequencies, and do a second scan.

What You Should Try Next

If you understood this, you're ready to tackle related problems:

• First Repeating Character

• First Non-Repeating Character in a Stream

• Find All Duplicates

And always ask: Can I break this into two passes? Can I track counts efficiently?

Happy coding!