How do you find the first non-repeating character in a string?
SHORT ANSWER
Count how often each character appears in one pass, then scan again and return the first character whose count is 1.
Explain it simply
Think of the first person in a queue who has no twin standing anywhere else in the line. You cannot know that by looking at one person; you need the whole headcount first.
So do two passes: the first pass counts every letter, the second walks in the original order and stops at the first letter that was counted once.
Example
js
function firstUniqueChar(s) {
const count = new Map();
for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1);
for (let i = 0; i < s.length; i++) {
if (count.get(s[i]) === 1) return i;
}
return -1;
}
console.log(firstUniqueChar("swiss")); // Output: 1
console.log(firstUniqueChar("loveleetcode")); // Output: 2
console.log(firstUniqueChar("aabb")); // Output: -1Complexity
Time O(n), space O(k) for k distinct characters.
What to say in the interview
"I do two passes. The first builds a frequency map, the second goes through the string in order and returns the index of the first character with count one, or -1. Time is O(n), and space is O(1) for a fixed alphabet or O(k) for k distinct characters."
Common mistakes
- Using indexOf and lastIndexOf in a loop, which is O(n squared).
- Iterating over the map instead of the string, which loses the original order if keys are not in string order.