First Unique Character in a String

First Unique Character in a String

1. What is this problem about?

The First Unique Character in a String interview question asks you to find the first character in a string that does not repeat anywhere else. You should return its 0-based index. If every character appears at least twice, return -1.

2. Why is this asked in interviews?

This is a standard introductory question for companies like Amazon and Apple. It tests your ability to use Hash Tables for frequency counting and your understanding of multi-pass algorithms. It evaluation if you can balance the time complexity of counting versus the time complexity of searching.

3. Algorithmic pattern used

This problem follows the Two-pass Frequency Counting pattern.

1. Pass 1: Iterate through the string and record the frequency of each character in a hash map or an array of size 26.
2. Pass 2: Iterate through the string again. For each character, check its frequency in the map.
3. Result: The first character with a frequency of 1 is the answer. Return its current index.
4. Default: If the loop ends, return -1.

4. Example explanation

String: "loveleetcode"

1. Counts: l:2, o:2, v:1, e:4, t:1, c:1, d:1
2. Pass 2:
   • 'l': freq 2.
   • 'o': freq 2.
   • 'v': freq 1. Found! Result index: 2.

5. Common mistakes candidates make

• One-pass confusion: Trying to find the unique character in a single pass without storing sufficient state (like indices or a linked hash map).
• Nested loops: Using $O(N^2)$ to check every character against the rest of the string.
• Returning the character: Accidentally returning the character 'v' instead of its index 2.

6. Interview preparation tip

For string problems with a fixed alphabet, always mention that an array of size 26 is more space-efficient than a Hash Map. This shows you understand low-level memory usage. This is a vital Hash Table interview pattern.