06. First Non-Repeating Character in a String

Difficulty:EasyPattern:Two-Pass Hash MapTime:O(n)Space:O(1)

Find the first non-repeating character in a string and return its index. If it does not exist, return -1.

How It Works & Algorithmic Design

This requires a Two-Pass Algorithm using a Frequency Map:

First Pass (Counting): Iterate through the string from index $0$ to $n-1$ and build a frequency dictionary mapping each character to its occurrence count.
Second Pass (Position Lookup): Iterate through the string a second time from left to right. Look up each character's count in the frequency map. The first character with a count equal to 1 is our answer; return its current loop index.
Fallback: If all characters have counts $> 1$, return -1.

Why This Approach Works Best

Checking every character against the rest of the string using nested loops takes $O(n^2)$ time. The two-pass Hash Map pattern reduces the time complexity to optimal linear $O(n)$ while taking $O(1)$ space for fixed alphabets.

Example Walkthrough

Input: "leetcode"

Target string.

Pass 1 (Counts): { l:1, e:3, t:1, c:1, o:1, d:1 }

Frequency table built.

Pass 2 (Lookup): Index 0 = 'l', count is 1 -> Found!

Returns index 0.

Output: 0

First unique character is 'l' at index 0.

Answer: First unique character search

function firstUniqChar(s) {
  const count = {};
  for (const ch of s) count[ch] = (count[ch] || 0) + 1;
  for (let i = 0; i < s.length; i++) {
    if (count[s[i]] === 1) return i;
  }
  return -1;
}

💡 Build frequency counts first, then locate the first character with a count of 1.

Key Takeaways

Two-pass linear scans preserve original order while accumulating global frequencies.
Time complexity is $O(2n) = O(n)$.
Space complexity remains $O(1)$ when bounded by character set limits (e.g., ASCII/English letters).