Find the first non-repeating character in a given string

Count character frequencies in one pass, then scan the string again and return the first character with a count of 1. O(n) time, O(k) space where k is the alphabet size.

4 min read·~12 min to think through

Classic two-pass frequency problem. The key insight: you need order preserved, so a hash map of counts plus a second scan of the original string.

Approach

First pass — build a frequency map of every character.
Second pass — walk the string in order, return the first char whose count is 1.
If none, return null (or -1 for an index).

function firstNonRepeating(str) {
  const counts = new Map();
  for (const ch of str) {
    counts.set(ch, (counts.get(ch) ?? 0) + 1);
  }
  for (const ch of str) {
    if (counts.get(ch) === 1) return ch;
  }
  return null;
}

Why two passes, not one?

A single pass can't know if a character repeats later. You must finish counting before deciding. (You can do one logical pass with a Map of {count, index} then find the min index with count 1 — still O(n), just different bookkeeping.)

Complexity

Time: O(n) — two linear scans.
Space: O(k) — k distinct characters (bounded by alphabet size, so effectively O(1) for ASCII).

Variations interviewers add

Return the index instead of the character.
Case-insensitive — normalize with toLowerCase() first.
Stream version — characters arrive over time; use a Map plus a queue/linked-list of candidate indices and pop from the front as they get invalidated.
Unicode — iterate with for...of (not index access) so surrogate pairs / emoji count as one character.

Follow-up questions

•How would you adapt this to a stream where characters arrive over time?
•Why does for...of matter for Unicode correctness here?
•Can you do it conceptually in one pass? What's the tradeoff?
•How would you return the index instead of the character?

Common mistakes

•Trying to decide in a single pass before all counts are known.
•Using indexOf/lastIndexOf inside a loop — that's O(n^2).
•Indexing the string by [i] and breaking emoji/surrogate pairs.
•Forgetting the no-result case and returning undefined implicitly.

Performance considerations

•Two O(n) passes beat the naive O(n^2) of nested scans or indexOf-in-loop. Map vs plain object is mostly a wash for char keys; Map iteration order is insertion order which can simplify the stream variant.

Edge cases

•Empty string → null.
•All characters repeat → null.
•Single character → that character.
•Whitespace and punctuation count as characters unless told otherwise.

Real-world examples

•Detecting the first unique token in a log line.
•Streaming uniqueness checks in data pipelines.

Senior engineer discussion

Seniors immediately state the two-pass O(n) bound, note the one-pass-with-bookkeeping equivalent, and pre-empt the Unicode trap (for...of vs index access). The interesting extension is the streaming variant — it tests whether you can maintain a queue of still-valid candidates and reason about amortized cost.