First Unique Character in a String

easy string hash map counting

Problem

Given a string s, return the index of the first non-repeating character. If it does not exist, return -1.

Inputs = "leetcode"

Output0

'l' appears once and is the leftmost such character.

def first_uniq_char(s):
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for i, c in enumerate(s):
        if count[c] == 1:
            return i
    return -1

function firstUniqChar(s) {
  const count = new Map();
  for (const c of s) count.set(c, (count.get(c) || 0) + 1);
  for (let i = 0; i < s.length; i++) {
    if (count.get(s[i]) === 1) return i;
  }
  return -1;
}

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

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

Explanation

To find the first letter that shows up only once, we use two passes over the string. The first pass tallies how often each character appears; the second pass walks left to right and returns the index of the first character whose tally is 1.

Why two passes? Because on the very first scan we cannot yet know whether a character will repeat later. By counting everything first, the second scan has the full picture and can decide instantly with a simple lookup.

We store the counts in a hash map (or a fixed array of 26 slots for lowercase letters). Building it is count[c] = count.get(c, 0) + 1 for every character, which is one cheap operation each.

Example: s = "leetcode". Counts become l:1, e:3, t:1, c:1, o:1, d:1. On the second pass the first character l already has count 1, so we return index 0.

If we reach the end without finding any count-1 character, every letter repeats, so we return -1.

Time: O(n) Space: O(k) (alphabet size)