Skip to main content
CodePeet

First Unique Character in a String

Try it yourself
EasyProblemExternal link

Description

You get a string s.

Find the first character in it that doesn't repeat, and return its index. If every character repeats, return -1.

Examples

Example 1

Input: s = "leetcode"

Output: 0

Explanation: l appears once, and nothing comes before it: index 0.

Example 2

Input: s = "loveleetcode"

Output: 2

Explanation: l and o both appear twice; v, at index 2, appears once.

Example 3

Input: s = "aabb"

Output: -1

Explanation: Every letter appears twice, so there's no answer: -1.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s consists of only lowercase English letters.

Editorial

Brute Force

Intuition

Take the letters in order. For each one, count how many times it appears in the whole string. The first letter whose count is 1 is the answer.

Step-by-Step Explanation

Let's try s = "loveleetcode":

  1. Walk all 12 letters, counting the l's. There are 2, so l repeats. Try the next index.
  2. Walk all 12 letters, counting the o's. There are 2, so o repeats. Try the next index.
  3. Walk all 12 letters, counting the v's. There is just the one, so index 2 is the answer.

Count Each Letter From Scratch — Each step counts one letter across the whole string: the current letter, and every other copy of it in amber.

Algorithm

  1. For each index i: count how many j have s[j] == s[i].
  2. If the count is 1, return i.
  3. If no index has a count of 1, return -1.

Code

class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            int k = 0;
            for (int j = 0; j < n; j++)         // count s[i] by walking the whole string
                if (s[j] == s[i]) k++;
            if (k == 1) return i;
        }
        return -1;
    }
};

class Solution:
    def firstUniqChar(self, s: str) -> int:
        n = len(s)
        for i in range(n):
            k = 0
            for j in range(n):                  # count s[i] by walking the whole string
                if s[j] == s[i]:
                    k += 1
            if k == 1:
                return i
        return -1

class Solution {
    public int firstUniqChar(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int k = 0;
            for (int j = 0; j < n; j++)         // count s[i] by walking the whole string
                if (s.charAt(j) == s.charAt(i)) k++;
            if (k == 1) return i;
        }
        return -1;
    }
}

var firstUniqChar = function(s) {
    const n = s.length;
    for (let i = 0; i < n; i++) {
        let k = 0;
        for (let j = 0; j < n; j++)             // count s[i] by walking the whole string
            if (s[j] === s[i]) k++;
        if (k === 1) return i;
    }
    return -1;
};

Complexity Analysis

Time Complexity: O(n²)

Every index walks the whole string again.

Space Complexity: O(1)

Why This Approach Is Not Efficient

With 10^5 letters that's 10^10 comparisons (over the time limit in cpp and Python and java and javascript).

And the counts it recomputes never change: the count of l is the same whichever l you're looking at. Count every letter once, then look the counts up.

Optimal Approach - Count, Then Scan

Intuition

Two passes. The first counts every letter (26 counters). The second walks the string again, in order, and returns the first index whose letter has a count of 1.

Why not one pass? When you meet a letter you can't know yet whether a later copy is coming. And why scan the string, not the counts? "First" means first in the string, and a hash map doesn't keep the string's order (see the second mistake below).

Step-by-Step Explanation

Let's try s = "loveleetcode" again:

  1. Pass 1 counts every letter once, in 12 steps.
  2. Pass 2 reaches index 0, l, whose count is 2. It repeats, so keep going.
  3. Pass 2 reaches index 1, o, whose count is 2. It repeats, so keep going.
  4. Pass 2 reaches index 2, v, whose count is 1. That's 1, so the answer is 2.

Count Once, Then Scan — Below the string is every letter's count. The second pass walks the string and looks each letter up.

Algorithm

  1. Count every letter of s into an array of 26.
  2. For each index i, in order: if the count of s[i] is 1, return i.
  3. Return -1.

Code

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26] = {0};                    // pass 1: how often each letter appears
        for (char c : s) count[c - 'a']++;
        for (int i = 0; i < (int)s.size(); i++) // pass 2: the string, in order
            if (count[s[i] - 'a'] == 1) return i;
        return -1;
    }
};

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = [0] * 26                        # pass 1: how often each letter appears
        for c in s:
            count[ord(c) - ord('a')] += 1
        for i, c in enumerate(s):               # pass 2: the string, in order
            if count[ord(c) - ord('a')] == 1:
                return i
        return -1

class Solution {
    public int firstUniqChar(String s) {
        int[] count = new int[26];              // pass 1: how often each letter appears
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (int i = 0; i < s.length(); i++)    // pass 2: the string, in order
            if (count[s.charAt(i) - 'a'] == 1) return i;
        return -1;
    }
}

var firstUniqChar = function(s) {
    const count = new Array(26).fill(0);        // pass 1: how often each letter appears
    for (const c of s) count[c.charCodeAt(0) - 97]++;
    for (let i = 0; i < s.length; i++)          // pass 2: the string, in order
        if (count[s.charCodeAt(i) - 97] === 1) return i;
    return -1;
};

Complexity Analysis

Time Complexity: O(n)

Two passes over the string.

Space Complexity: O(1)

26 counters, whatever the length.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Comparing each letter with its neighbours only. if s[i - 1] != c and s[i + 1] != c: return i

On s = "abca", it returns 0; the answer is 1. A letter can repeat far away: in "abca" the a at index 0 has different neighbours, but there's another a at the end. Count every letter over the whole string.

Walking the hash map for the first count of 1 (C++). for (auto& [c, k] : count) if (k == 1) return s.find(c);

On s = "loveleetcode", it returns 10; the answer is 2. A hash map walks its keys in its own order, not the string's: on "loveleetcode" an unordered_map can offer d before v. Scan the string itself for the first letter with a count of 1.

Scanning from the end. for i in range(len(s) - 1, -1, -1):

On s = "loveleetcode", it returns 10; the answer is 2. Scanning from the end finds a letter that appears once, but the question asks for the first one.

Where This Pattern Is Taught

This problem practises counting with a hash table, then scanning in order. It's taught in Frequency Counting with Hash Maps.