First Unique Character in a String - Solution & Explanation
Problem Statement
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 <= 105sconsists of only lowercase English letters.
Approach Overview
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 1: Approach 1: Using a Frequency Map
This approach employs a hash map to store the frequency of each character in the string. Then, by iterating through the string again, we can find the first character with a frequency of 1 and return its index. If no such character is found, we return -1.
The function firstUniqChar tracks the frequency of each character in the string using an integer array. The first loop fills up the frequencies, and the second loop finds the first character with a frequency of one, returning its index. If no such character is present, it returns -1.
Complexity
Time Complexity: O(n), where n is the length of the string, as we traverse through the string twice.
Space Complexity: O(1), because the array size is constant (26 letters of the English alphabet).
Approach 2: Approach 2: Using Two Iterations Without Hash Map
This approach involves iterating through the input string two times without using any auxiliary space like a hash map or dictionary. In the first iteration, we use an array to count the occurrences of each character. In the second iteration, we check for the first character that appears only once by referring to the count array. We conclude by returning its index or -1 if no such character is found.
The C solution involves a simple integer array of size 26, corresponding to each lowercase letter, and populating it with frequencies of the characters present. By going over the string a second time, the index of the first non-repeating character is identified.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Counting
We use a hash table or an array of length 26 cnt to store the frequency of each character. Then, we traverse each character s[i] from the beginning. If cnt[s[i]] is 1, we return i.
If no such character is found after the traversal, we return -1.
The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, the character set consists of lowercase letters, so |\Sigma|=26.
Code
Python
Java
C++
Go
TypeScript
JavaScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Frequency Map | Time Complexity: O(n), where n is the length of the string, as we traverse through the string twice. |
| Approach 2: Using Two Iterations Without Hash Map | Time Complexity: O(n) |
| Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
First Unique Character in String | Easy - Leetcode387 • Shradha Khapra • 50,368 views views
Watch 9 more video solutions →Frequently Asked Questions
Is First Unique Character in a String easy or hard?
First Unique Character in a String Python/Java solution
How to solve First Unique Character in a String in O(n)?
What is the best approach for First Unique Character in a String?
Is First Unique Character in a String asked at Google/Amazon/Meta?
What data structure is used in First Unique Character in a String?
What is the time complexity of First Unique Character in a String?
Ready to solve this problem?
Practice First Unique Character in a String with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor