Problem statement

Given a string s, find the first character that does not repeat anywhere in the string and return its index. If there is no such character, return -1.

Example 1

Input: s = "leetcode"
Output: 0
Explanation: l occurs once and is first.

Example 2

Input: s = "loveleetcode"
Output: 2
Explanation: v is the first character with a count of one.

Example 3

Input: s = "aabb"
Output: -1

Constraints

• 1 <= s.length <= 40
• s consists of lowercase English letters.

Hints for First Unique Character in a String

1. Hint 1

   You cannot know a character is unique until you have seen the whole string — so make two passes.

2. Hint 2

   First pass: tally the 26 letter counts. Second pass: return the index of the first letter whose tally is 1.

3. Hint 3

   Scanning in index order during the second pass is what makes it the first such character.

How to solve First Unique Character in a String

Uniqueness is only known once the whole string has been read, so tally the letters first and then scan again for the first tally of 1.

Approach

1. Count each of the 26 letters.
2. Walk the string in order and return the index of the first character whose count is 1.
3. Return -1 if none.

Why it works

The second pass visits indices in increasing order, so the first hit is the leftmost non-repeating character.

Complexity

• Time — O(n)
• Space — O(1) — 26 counters

Pitfalls

• A single pass with a set of "seen once" values is tempting but cannot know a later duplicate.
• Use a hash map instead of the fixed array for Unicode input.

Reference solution

Python

def firstUniqChar(s: str) -> int:
    count = [0] * 26
    for ch in s:
        count[ord(ch) - 97] += 1
    for i, ch in enumerate(s):
        if count[ord(ch) - 97] == 1:
            return i
    return -1

Java

public static int firstUniqChar(String s) {
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
    for (int i = 0; i < s.length(); i++) {
        if (count[s.charAt(i) - 'a'] == 1) return i;
    }
    return -1;
}

C++

int firstUniqChar(string s) {
    int count[26] = {0};
    for (char ch : s) count[ch - 'a']++;
    for (int i = 0; i < (int) s.size(); i++) {
        if (count[s[i] - 'a'] == 1) return i;
    }
    return -1;
}

JavaScript

var firstUniqChar = function(s) {
    const count = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
    for (let i = 0; i < s.length; i++) {
        if (count[s.charCodeAt(i) - 97] === 1) return i;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy