#387 First Unique Character in a String

frequently reported atGoldman Sachs Bloomberg Walmart Amazon Apple

the problem

In plain words

s contains only lowercase letters. Find the first character that appears exactly once in the whole string and return its index. If every character repeats, return -1.

in s = "leetcode"

out 0

'l' appears only once.

in s = "loveleetcode"

out 2

'l' and 'o' repeat; 'v' at index 2 doesn't.

in s = "aabb"

out -1

1 ≤ s.length ≤ 10⁵
Lowercase English letters only

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFrequency counting

"Appears once" needs the whole string; "first" needs the order. So two passes: count everything, then walk s in order and return the first letter whose count is 1.

solutions

From brute force to optimal

For each position, scan the string for the same letter somewhere else.

For each i, loop j over the string (j ≠ i).
If s[j] == s[i], it repeats — move on.
The first i with no match is the answer.

timeO(n²)

Up to n scans of n chars — 10¹⁰ steps at n = 10⁵.

spaceO(1)

Two indexes.

javajava.util.*

1class Solution {2    public int firstUniqChar(String s) {3        for (int i = 0; i < s.length(); i++) {4            boolean repeated = false;5            for (int j = 0; j < s.length(); j++) {6                if (j != i && s.charAt(j) == s.charAt(i)) {   // same letter somewhere else7                    repeated = true;8                    break;9                }10            }11            if (!repeated) return i;12        }13        return -1;14    }15}

Count letters in a HashMap<Character, Integer>, then scan in order.

count.merge(c, 1, Integer::sum) for every char.
Return the first i with count.get(s.charAt(i)) == 1.

timeO(n)

Two passes, O(1) average per map operation.

spaceO(1)

At most 26 keys — but each key and value is a boxed object.

javajava.util.*

1class Solution {2    public int firstUniqChar(String s) {3        Map<Character, Integer> count = new HashMap<>();4        for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum); // boxes c and the count5        for (int i = 0; i < s.length(); i++) {6            if (count.get(s.charAt(i)) == 1) return i;   // Integer == int unboxes: safe here7        }8        return -1;9    }10}

Same two passes, but c - 'a' turns each letter into an index of a plain array.

count = new int[26].
Pass 1: count[s[i] − 'a']++.
Pass 2: first i with count[s[i] − 'a'] == 1.
Otherwise −1.

timeO(n)

Two passes of array increments — no hashing, no boxing.

spaceO(1)

26 ints, whatever the length of s.

javajava.util.*

1class Solution {2    public int firstUniqChar(String s) {3        int[] count = new int[26];                    // one counter per letter4        for (int i = 0; i < s.length(); i++) {5            count[s.charAt(i) - 'a']++;               // 'a'->0 ... 'z'->256        }7        for (int i = 0; i < s.length(); i++) {        // second pass, in string order8            if (count[s.charAt(i) - 'a'] == 1) {      // seen exactly once?9                return i;10            }11        }12        return -1;                                    // every letter repeats13    }14}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int firstUniqChar(String s) {3        int[] count = new int[26];                    // one counter per letter4        for (int i = 0; i < s.length(); i++) {5            count[s.charAt(i) - 'a']++;               // 'a'->0 ... 'z'->256        }7        for (int i = 0; i < s.length(); i++) {        // second pass, in string order8            if (count[s.charAt(i) - 'a'] == 1) {      // seen exactly once?9                return i;10            }11        }12        return -1;                                    // every letter repeats13    }14}

in the room

How to say it in the interview

talk track

Clarify: lowercase only? (Yes — that's what allows int[26].)
Mention the O(n²) idea in one line, then the two-pass count: O(n) time, O(1) space because the alphabet is fixed.
Explain why pass 2 walks s and not the count array: the count array is in alphabet order, the answer needs string order.

traps

Walking the count array in pass 2 returns the alphabetically first unique letter, not the first one in s.
c - 'a' on an uppercase letter or digit goes negative → ArrayIndexOutOfBoundsException.

what they ask next

Follow-ups

Characters arrive as a stream and you must answer after each one?

Keep the counts plus a queue of candidates; after each char, pop from the front while the front's count is above 1. Each char enters and leaves once: O(1) amortised.

Full Unicode instead of a–z?

Use a HashMap<Character, Integer> — the two-pass idea doesn't change.

before you submit

Edge cases to test

No unique letter ("aabb") → −1.
The unique letter is the very last one ("aabbc") → 4.
A single character → 0.

practise next