387. First Unique Character in a String - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

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

Examples:

Example 1
- Input:
```
s = "leetcode"
```
- Output:
```
0
```
- Explanation:
  The character 'l' at index 0 appears only once in the string.
Example 2
- Input:
```
s = "loveleetcode"
```
- Output:
```
2
```
- Explanation:
  The characters and their frequencies are:
  'l' → 2, 'o' → 2, 'v' → 1, 'e' → 4, ...
  The first unique character is 'v' at index 2.
Example 3
- Input:
```
s = "aabb"
```
- Output:
```
-1
```
- Explanation:
  Every character appears at least twice, so there is no unique character.

Constraints:

Frequency Count:
Count the occurrences of each character in the string. This can be done efficiently using a hash map (or an array of size 26 since we only have lowercase letters).
Two-Pass Solution:
- First Pass: Compute the frequency for every character.
- Second Pass: Traverse the string again and return the index of the first character with a frequency of 1.
Optimizing:
An optimal solution runs in O(n) time by using extra space for the frequency counter.

Idea:
For every character, iterate through the entire string to count its occurrences.
Steps:
1. For each character in the string, count its total appearances by iterating over the string.
2. Return the index of the first character that appears only once.
Downside:
This approach leads to a time complexity of O(n²), which is not efficient for longer strings.

Idea:
Use a frequency counter to record the number of times each character appears, then iterate over the string to find the first character with a count of 1.
Steps:
1. First Pass:
  Traverse the string and count the frequency of each character.
2. Second Pass:
  Traverse the string again and check the frequency counter. Return the index of the first character that occurs only once.
3. If no such character exists, return -1.
Time Complexity:
O(n) – one pass to count and one pass to check.
Space Complexity:
O(1) – since the frequency counter uses a fixed size of 26 (for lowercase letters).

Let's consider s = "loveleetcode".

Frequency Count (First Pass):
- Traverse the string and count occurrences:
  - 'l' → 2
  - 'o' → 2
  - 'v' → 1
  - 'e' → 4
  - 't' → 1
  - 'c' → 1
  - 'd' → 1
Identify the First Unique Character (Second Pass):
- Iterate over the string:
  - Index 0: 'l' (frequency 2) → Not unique.
  - Index 1: 'o' (frequency 2) → Not unique.
  - Index 2: 'v' (frequency 1) → Unique! Return index 2.

Python3

. . . .

Java

. . . .

Time Complexity:
- The first pass iterates over the string once: O(n).
- The second pass iterates over the string once: O(n).
- Total: O(n)
Space Complexity:
- We use an array (or hash map) of constant size (26 for lowercase letters): O(1)

Not Handling the Case When No Unique Character Exists:
- Ensure your code returns -1 if every character appears more than once.
Ignoring Case Sensitivity:
- The problem specifies lowercase letters, but if the input may include uppercase letters, adjustments are needed.
Inefficient Solutions:
- Avoid checking each character against every other character, which leads to O(n²) complexity.

First Repeating Character:
Find the first character that repeats in a string.
Longest Substring Without Repeating Characters:
Determine the length of the longest substring without duplicate characters.
Group Anagrams:
Group a list of strings into anagrams.
Character Frequency Problems:
Many problems revolve around counting characters and making decisions based on their frequencies.