First Unique Character in a String

Search Insert Position

Is Subsequence

Find the index of the first non-repeating character in a string.

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

## Example
```
Input: s = "leetcode"
Output: 0

Input: s = "loveleetcode"
Output: 2
```

Constraints:
- `1 <= s.length <= 10^5`
- `s` consists of only lowercase English letters.

**Follow-up**
Can you do it in a single pass if the alphabet were unknown or much larger than lowercase English letters, without changing the overall O(n) time bound?

- Return the index of the first character that appears exactly once.
- If every character repeats, return `-1`.
- Since the first unique character depends on original order, we must preserve or revisit indices.

Understand the Goal

- For each character, scan the whole string to count how many times it appears.
- The first character with count one is the answer.
- This works, but it can take O(n²) time for long strings.

Consider the Naive Approach

- Build a frequency map in one pass so each character count is available quickly.
- Then make a second pass through the string in original order.
- The first index whose character has count one is the required answer.

Count Frequencies First

- The first pass answers the question: how many times does each character appear?
- The second pass answers the question: which unique character appears first?
- Separating these keeps the algorithm simple and linear.

Why Two Passes Are Useful

- Time complexity is O(n) because the string is traversed twice.
- Space complexity is O(1) if limited to lowercase English letters, otherwise O(k) for distinct characters.
- Returning `-1` covers the case where no unique character exists.