A support inbox tagged each ticket with a campaign slug. Routing needed the first letter that appeared only once in that slug — a cheap badge for the queue board. The first version nested a scan: for each index, walk the whole slug again to see if that character repeats. Staging slugs of a dozen characters returned instantly. Production tracking tokens tens of thousands of characters long were still proving uniqueness when the worker’s lease expired.

First Unique Character asks for the first index whose character appears exactly once. s.charAt(i) is already free. Nested uniqueness uses that and still pays O(n²). A count answers “how many times?” once, then a second walk returns the first index of one.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about counting occurrences so the first unique is a lookup, not a restart.

The problem

Given a string s, return the index of the first character that appears exactly once. If every character repeats, return -1. Assume lowercase English letters unless a follow-up widens the alphabet.

s = "gadget"   →  1    'a' appears once; 'g' repeats
s = "pepper"   →  5    'r' is unique; 'p' and 'e' repeat
s = "coco"     → -1    every letter repeats

Note: Uniqueness looks both ways. Scanning only j > i is not a proof: the last 'p' in pepper has no later copy and is still a duplicate.

Nested uniqueness is the honest brute force

For each index, scan the whole string. If no other index holds the same character, that index is the answer. Correct. Quadratic.

int firstUniqCharNested(String s) {
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        boolean unique = true;
        for (int j = 0; j < s.length(); j++) {
            if (i != j && s.charAt(j) == c) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return i;
        }
    }
    return -1;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested uniqueness scan for a question a count answers in linear time: how many times does this character appear?

Count once, then walk for the first one

You cannot return on the first character that looks unique mid-pass — a later copy may still arrive. Walk the string and increment a map (or a 26-slot array). Walk again from the left. The first index whose count is 1 is the answer. If none, -1.

You never restart a uniqueness scan from index 0. You never return a character when the prompt asked for an index. A 26-slot array is the same idea when the alphabet is lowercase English.

s = "gadget"

count:  g:2 a:1 d:1 e:1 t:1

i=0  g  count=2  skip
i=1  a  count=1  return 1

The Java is that walk:

int firstUniqChar(String s) {
    Map<Character, Integer> count = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        count.put(c, count.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
        if (count.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

Time is expected O(n) — two passes, one expected-O(1) lookup or put per index. Space is O(1) for a 26-letter alphabet (a map of lowercase English is the same bound). Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Return the index, not the character. gadget answers 1, not 'a'. Stopping at the first character without a finished count is the same mistake as the nested scan: 'g' is first, and it is not unique.

What interviewers usually poke next

  • No unique character. Return -1. coco is not an error; it is a complete answer.
  • Unicode, not just a–z. The 26-slot array is a lie. Use a map, same count-then-walk, unbounded keys.
  • Valid Anagram. Same count, different question: anagram asks whether two frequency tables match; this prompt asks for the first index whose count is 1.
  • Cover counts, not first unique. Can one string’s letter bag cover another’s? Same frequency table, still not the first index whose count is 1.

You are done with this problem when you can say, out loud, why the nested uniqueness scan is correct and why a count-then-first-index walk is the expected answer.