Write a function that returns the first non-repeating character in a string.
Count how many times each character appears using a Map in one pass, then scan the string a second time and return the first character whose count is 1. Return null if none exists.
Explain it simply
Picture an attendance register where you tally how many times each name was called. Then you read the register from the top and stop at the first name with a tally of exactly one.
Two passes are needed because you cannot know a character is unique until you have seen the whole string. A Map keeps counts, and because the second pass walks the original string in order, the first match is automatically the earliest one.
A nested loop comparing every pair also works but takes quadratic time.
Line by line
function firstUnique(str) {
const count = new Map();
for (const ch of str) {
count.set(ch, (count.get(ch) || 0) + 1);
}
for (const ch of str) {
if (count.get(ch) === 1) return ch;
}
return null;
}
console.log(firstUnique("swiss")); // Output: w
console.log(firstUnique("leetcode")); // Output: l
console.log(String(firstUnique("aabb"))); // Output: nullWhat to say in the interview
"I make one pass to build a frequency Map, and a second pass over the original string to return the first character with count 1, otherwise null. It is O(n) time, and the space is bounded by the alphabet size."
Complexity
Time O(n) with two passes. Space O(k) for k distinct characters, effectively constant for a fixed alphabet.
Common mistakes
- Looping over the Map instead of the string, which gives insertion order of first sight only by luck of the data.