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.
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.
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).
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.
Time Complexity: O(n)
Space Complexity: O(1)
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.
Python
Java
C++
Go
TypeScript
JavaScript
PHP
| 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 | — |
| 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. |
First unique character in a string | Leetcode #387 • Techdose • 46,760 views views
Watch 9 more video solutions →Practice First Unique Character in a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor