First Unique Character in a String

The problem. Given a string s of lowercase letters, find the first character that appears exactly once and return its index. If there is none, return -1.

Example

s = "leetcode"        ->  0    ("l" appears once)
s = "loveleetcode"    ->  2    ("v")
s = "aabb"            ->  -1

The idea: count first, then scan

Whether a letter is unique depends on the whole string — the second copy might be the very last character. So one pass can't decide as it goes. Two passes can: the first counts every letter, the second walks the string in order and returns the first position whose letter has count 1. The counts turn "does this appear anywhere else?" from a search into an O(1) lookup.

1. Brute force: check every letter against every other

1function firstUniqChar(s) {2  for (let i = 0; i < s.length; i++) {3    let repeated = false;4    for (let j = 0; j < s.length; j++) {5      if (i !== j && s[i] === s[j]) {         // the same letter somewhere else6        repeated = true;7        break;8      }9    }10    if (!repeated) return i;11  }12  return -1;13}

Time O(n²), space O(1). Every letter may be compared with every other one.

2. Count, then scan

1function firstUniqChar(s) {2  const count = new Array(26).fill(0);3  for (const ch of s) count[ch.charCodeAt(0) - 97]++;   // pass 1: count every letter4  for (let i = 0; i < s.length; i++) {5    if (count[s.charCodeAt(i) - 97] === 1) return i;    // pass 2: the first letter seen once6  }7  return -1;8}

Time O(n), space O(1). Two passes over the string; the 26 counters don't grow with the input.

Comparing the approaches

For a stream of characters you can't scan twice: keep the counts plus a queue of candidates in arrival order, and pop from the front while its count is above 1. The front of the queue is always the current first unique character.

Edge cases to test

Variations