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.The key idea in #387 First Unique Character in a String is to identify the first character whose frequency in the string is exactly one. Since we must check character occurrences efficiently, a common strategy is to use a hash table (frequency map) to count how many times each character appears.
In the first pass, iterate through the string and store counts of each character in a HashMap or fixed-size array (since the input is typically lowercase letters). In the second pass, traverse the string again and return the index of the first character whose count equals 1. This works because the original order of characters must be preserved.
An alternative approach combines a queue with a frequency map. As characters are processed, unique candidates are added to the queue, while repeated characters are removed from consideration. The queue’s front always represents the earliest potential unique character.
Both strategies achieve linear performance, making them efficient for large strings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map / Frequency Counting | O(n) | O(1) to O(k) depending on character set |
| Hash Map + Queue | O(n) | O(k) |
Kevin Naughton Jr.
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.
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).
1import java.util.HashMap;
2
3public class FirstUniqueCharacter {
4 public static int firstUniqChar(String s) {
5
This Java solution iterates through the string and populates a HashMap with the frequency of each character. We then iterate through the string again and return the index of the first character with a frequency of 1.
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.
Time Complexity: O(n)
Space Complexity: O(1)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
It is possible but inefficient. Without extra storage, you would need to repeatedly scan the string to check frequencies, resulting in O(n^2) time complexity, which is not ideal for interviews.
Yes, this problem or its variations frequently appear in coding interviews at major tech companies. It tests understanding of hash tables, frequency counting, and efficient string traversal.
A hash table (or a fixed-size frequency array for lowercase letters) is the most efficient data structure. It allows constant-time updates and lookups while counting character occurrences.
The optimal approach uses a hash table to count the frequency of each character in the string. After counting, a second pass finds the first character with frequency equal to one. This method runs in O(n) time and is simple to implement.
A Java array of size 26 counts letters' frequencies, permitting the identification of the first unique character in a subsequent loop that reiterates through the string.