First Unique Character in a String easy

Description

Given a string s, find the first non-repeating character and return its index. If there is no such character, return -1.

Examples

> Case 1:
    Input:  s = "leetcode"
    Output: 0       # 'l' is the first character to appear only once
 
> Case 2:
    Input:  s = "loveleetcode"
    Output: 2       # 'v' is the first non-repeating; 'l' and 'o' appear twice
 
> Case 3:
    Input:  s = "aabb"
    Output: -1

Constraints

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

Intuition

Two passes:

1. First pass — count frequencies. Build {char: count} by walking the whole string. O(n).
2. Second pass — find the first single. Walk the string again, return the index of the first character whose count is 1. O(n).

Total: O(n) time, O(1) space (the count map has at most 26 entries because we’re told it’s lowercase ASCII).

You can’t do it in one pass because “the first character with count 1” depends on the final count — and you don’t know that until you’ve seen the whole string.

Code

#include <string>
#include <vector>
using namespace std;
 
int firstUniqChar(string s) {
    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++) {
        if (freq[s[i] - 'a'] == 1) return i;
    }
    return -1;
}

from collections import Counter
 
def first_uniq_char(s):
    freq = Counter(s)
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

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

Why two passes is the right call

You might think: “what if I track the first occurrence and decrement as we see duplicates?” That gets messy fast — you need to remember which index was the candidate, then push it forward when duplicates appear, then handle the no-unique case. Two clean passes is simpler and just as fast.

Variant: streaming version

What if the input is a stream and you have to answer “first non-repeating character so far” after every character? That’s harder — you need to maintain an ordered set of single-occurrence characters as the stream advances. The standard solution uses a LinkedHashMap (Java), OrderedDict (Python), or a doubly linked list keyed by the character (C++).

Analysis

• Time: O(n) — two passes through the string.
• Space: O(1) when the alphabet is bounded; O(k) where k is the number of distinct characters in the general case.