First Unique Character in a String

1. Define the problem

First Unique Character in a String

Given a string s, find the first character that does not repeat and return its index. If there is no such character, return -1. This needs two passes over the string. The first pass builds a hash map from character to how many times it appears anywhere in the string. The second pass walks the string in order and returns the index of the first character whose tally is exactly 1. Walking in order is what makes the answer the first one and not just any one.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters

Example

Inputs = "aabbcdd"

Output4

Explanation a, b and d all appear twice. Only c appears once, and it sits at index 4, so the answer is 4.

2. Know the words first

In plain terms

Unique character: A character that appears exactly once in the whole string. Its tally in the count map is 1.
Index: The position of a character in the string, counting from 0. In "abc" the character b sits at index 1.
Two pass: Reading the input twice: once to gather facts, once to act on them. The first pass has to finish before the second can be trusted, because a character may repeat much later.

3. Visualize the solution

One cell per character key, value = how many times it appears

a—

b—

c—

d—

Statusinit

The count map starts empty for the string "aabbcdd".

What happens in this step

s = "aabbcdd"
indexes:  0123456

counts = empty
The four cells are the four different characters the string uses.

Step 1 of 6

Steps to visualize

The cells are the keys of the count map: label is the character, value is its tally.
Pass one: walk the whole string and add one to the tally of each character.
Pass two: walk the string again from index 0.
The first character whose tally reads 1 is the answer, and you return its index.
If pass two finishes with no tally of 1, return -1.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per character key, value = how many times it appears

a—

b—

c—

d—

Statusinit

The count map starts empty for the string "aabbcdd".

What happens in this step

s = "aabbcdd"
indexes:  0123456

counts = empty
The four cells are the four different characters the string uses.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function firstUniqChar(s) {
  const counts = new Map();

  for (const char of s) {
    counts.set(char, (counts.get(char) || 0) + 1);
  }

  for (let i = 0; i < s.length; i++) {
    if (counts.get(s[i]) === 1) {
      return i;
    }
  }

  return -1;
}

Time: O(n)
Space: O(1) because at most 26 character keys are stored

6. Test cases

Test cases

Input	Expected	Covers
`s = "aabbcdd"`	`4`	example from the description
`s = "leetcode"`	`0`	the very first character is already unique
`s = "loveleetcode"`	`2`	the answer is not the first character
`s = "aabb"`	`-1`	every character repeats, so the fallback runs
`s = "z"`	`0`	smallest input
`s = "aabbccddq"`	`8`	the only unique character sits at the last index

First Unique Character in a String