Find first unique character
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a lowercase/uppercase alphanumeric string s, return the index of the first character that appears exactly once; if none exists, return -1. Provide an O(n) approach and discuss space–time trade-offs against sorting-based solutions.
Quick Answer: Find first unique character evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a string s, return the index of the first character that appears exactly once. If no such character exists, return -1.
The comparison is case-sensitive (so 'a' and 'A' are different characters), and the string may contain alphanumeric characters.
Provide an O(n) approach. Compared to a sorting-based grouping, the hash-count approach preserves original order without storing extra index metadata and runs in O(n) instead of O(n log n).
Example 1:
Input: s = "leetcode"
Output: 0
('l' is the first character that appears exactly once.)
Example 2:
Input: s = "loveleetcode"
Output: 2
('v' at index 2 is the first character to appear exactly once.)
Example 3:
Input: s = "aabb"
Output: -1
(Every character repeats, so there is no unique character.)
Constraints
- 0 <= len(s) <= 10^5
- s consists of alphanumeric characters (comparison is case-sensitive).
- Return -1 when no character appears exactly once (including the empty string).
Examples
Input: ("leetcode",)
Expected Output: 0
Explanation: 'l' is the first character that appears exactly once, at index 0.
Input: ("loveleetcode",)
Expected Output: 2
Explanation: 'l','o','e' all repeat; 'v' at index 2 is the first character appearing exactly once.
Hints
- First pass: count how many times each character appears using a hash map.
- Second pass: walk the string in order and return the index of the first character whose count is 1.
- Scanning the original string (not the map) on the second pass is what preserves the 'first' / original-order requirement.
- A sorting-based approach groups equal characters but loses original order unless it also stores indices, and costs O(n log n) versus O(n) here.