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

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

Example Inputs & Outputs:

Example 1:
- Input: "leetcode"
- Output: 0
- Explanation:
  The first character 'l' appears only once, so its index 0 is returned.
Example 2:
- Input: "loveleetcode"
- Output: 2
- Explanation:
  The first unique character is 'v' at index 2. Although there are other unique characters, 'v' is the earliest in the string.
Example 3:
- Input: "aabb"
- Output: -1
- Explanation:
  Every character appears at least twice, so no unique character exists.

Constraints:

$( 1 \leq s.length \leq 10^5$ )
s consists of only lowercase English letters (in many cases; the problem may also include uppercase letters in variations).

Hint 1:
Think about how you might determine the frequency of each character in the string. This can help you quickly identify which characters appear only once.
Hint 2:
Once you have the frequency of each character, iterate through the string (in its original order) and check the frequency of each character. The first one with a frequency of 1 is your answer.

Idea:
For each character in the string, scan the rest of the string to check if it appears again.
Downside:
This approach requires nested iterations over the string, resulting in a time complexity of $(O(n^2)$ ), which is too slow for large inputs.

Idea:
Use a frequency counter (a dictionary or an array) to store the number of times each character appears in the string.
1. Count Frequencies:
  Iterate through the string once to build the frequency map.
2. Find the First Unique:
  Iterate through the string a second time and return the index of the first character whose frequency is 1.
Why It’s Optimal:
This method only requires two passes through the string (i.e., (O(n)) time) and uses extra space proportional to the number of distinct characters ((O(1)) if only lowercase English letters are used).

Python3

. . . .

Java

. . . .

Time Complexity:
- Counting Frequency: (O(n)), where (n) is the length of the string.
- Second Iteration: (O(n)) to find the first unique character.
- Overall: (O(n)).
Space Complexity:
- The frequency dictionary (or array) stores counts for at most a fixed set of characters (e.g., 26 lowercase letters), resulting in (O(1)) space if the character set is limited. Otherwise, (O(k)) where (k) is the number of distinct characters.

Example: "loveleetcode"

Frequency Counting:
- Iterate through "loveleetcode" and build the frequency map:
```
l: 2, o: 2, v: 1, e: 4, t: 1, c: 1, d: 1
```
Finding the First Unique:
- Iterate over the string in order:
  - Index 0: 'l' → frequency 2 (not unique)
  - Index 1: 'o' → frequency 2 (not unique)
  - Index 2: 'v' → frequency 1 (unique)
- Return index 2.

Visual Summary:

Index:      0    1    2    3    4   ...
Characters: l    o    v    e    l   ...
Frequency:  2    2    1    4    2   ...

The first unique character is 'v' at index 2.

Not Accounting for All Characters:
Forgetting to update the frequency correctly, especially when a character appears multiple times.
Not Handling the Case When No Unique Character Exists:
Failing to return -1 when all characters repeat.
Overlooking Edge Cases:
Such as an empty string (depending on problem constraints) or strings with a single character.

Empty String:
If the input string is empty (if allowed), the function should return -1.
All Characters Repeating:
For example, "aabbcc" should return -1 because no character is unique.
Single Character String:
A string like "z" should return 0 because that one character is unique.

Alternative Variations:
- Returning the unique character itself instead of its index.
- Handling strings with mixed case letters or Unicode characters.
Related Problems for Further Practice:
- Valid Anagram: Check if two strings are anagrams.
- Group Anagrams: Group strings that are anagrams.
- Longest Substring Without Repeating Characters: Find the longest substring without duplicate characters.