{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

First Unique Character in a String – Solution & Complexity

Interview solutions
/
First Unique Character in a String

Solution Walkthrough

  1. Step 1: Understand the Goal

    • Return the index of the first character that appears exactly once.
    • If every character repeats, return -1.
    • Since the first unique character depends on original order, we must preserve or revisit indices.

  2. Step 2: Consider the Naive Approach

    • For each character, scan the whole string to count how many times it appears.
    • The first character with count one is the answer.
    • This works, but it can take O(n²) time for long strings.
    def first_uniq_char(s):
    for i, char in enumerate(s):
        if s.count(char) == 1:
            return i
    return -1

  3. Step 3: Count Frequencies First

    • Build a frequency map in one pass so each character count is available quickly.
    • Then make a second pass through the string in original order.
    • The first index whose character has count one is the required answer.
    def first_uniq_char(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    for i, char in enumerate(s):
        if counts[char] == 1:
            return i
    return -1

  4. Step 4: Why Two Passes Are Useful

    • The first pass answers the question: how many times does each character appear?
    • The second pass answers the question: which unique character appears first?
    • Separating these keeps the algorithm simple and linear.

  5. Step 5: Final Complete Solution

    • Time complexity is O(n) because the string is traversed twice.
    • Space complexity is O(1) if limited to lowercase English letters, otherwise O(k) for distinct characters.
    • Returning -1 covers the case where no unique character exists.
    def first_uniq_char(s: str) -> int:
    counts = {}

    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for i, char in enumerate(s):
        if counts[char] == 1:
            return i

    return -1

FAQ

See also

Practice First Unique Character in a String online (run code in the browser)Find All Anagrams in a String solution (medium)Group Anagrams solution (medium)Isomorphic Strings solution (easy)Longest Substring Without Repeating Characters solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?