Watch 10 video solutions for First Unique Character in a String, a easy level problem involving Hash Table, String, Queue. This walkthrough by Kevin Naughton Jr. has 88,593 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = "leetcode"
Output: 0
Explanation:
The character 'l' at index 0 is the first character that does not occur at any other index.
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
1 <= s.length <= 105s consists of only lowercase English letters.Problem Overview: You receive a string s and must return the index of the first character that appears exactly once. If every character repeats, return -1. The challenge is identifying the first non‑repeating character while keeping the scan efficient.
Approach 1: Using a Frequency Map (O(n) time, O(n) space)
The standard solution counts how many times each character appears, then scans the string again to find the first character with frequency 1. Use a hash-based structure such as a dictionary or array counter. First pass: iterate through the string and increment counts in the frequency map. Second pass: iterate again and return the first index where the stored count equals 1.
This works because counting compresses the entire string into quick lookups. Each character check becomes an O(1) hash lookup. The total work is two linear scans, which gives O(n) time complexity and O(n) space for the frequency table. This approach relies heavily on hash tables and counting techniques commonly used in string problems.
Some implementations also maintain a queue of candidate indices while counting. As soon as a character’s frequency becomes greater than one, its index can be removed from the queue. The front of the queue always represents the current first unique candidate.
Approach 2: Two Iterations Without Hash Map (O(n²) time, O(1) space)
This method avoids extra memory by checking each character directly against the rest of the string. For every index i, iterate through the string and count how many times s[i] appears. If the count is exactly one, return i. If the character repeats, move to the next position and repeat the process.
The key idea is brute-force comparison. Because each character may trigger another full scan of the string, the worst-case complexity becomes O(n²). The advantage is constant extra memory (O(1)) since no map or auxiliary structure is used. This approach mainly demonstrates baseline reasoning when solving string problems.
Recommended for interviews: The frequency map solution is what interviewers expect. It demonstrates knowledge of hash-based counting and reduces the search to linear time. The brute-force approach still matters because it shows you understand the core requirement before optimizing. After stating the naive idea, move quickly to the O(n) counting strategy.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map (Hash Table) | O(n) | O(n) | General case. Best performance and standard interview solution. |
| Two Iterations Without Hash Map | O(n²) | O(1) | Useful for demonstrating brute-force reasoning or when avoiding extra memory. |