387. First Unique Character in a String
Model: qwen2.5-coder:14b
Topics: Hash Table,String
FAANG asked: 1
Acceptance rate: 53.9%
Problem Breakdown
The problem asks us to find the first non-repeating character in a given string s and return its index. If there are no unique characters, we should return -1. The input is a single string consisting of lowercase English letters, with a length constraint of between 1 and 10^5 characters.
Inputs:
- A string
scontaining only lowercase English letters.
Outputs:
- An integer representing the index of the first non-repeating character in the string.
- If no such character exists, return
-1.
Implicit Constraints/Edge Cases:
- The string can be as long as 10^5 characters, so the solution should be efficient in terms of time and space complexity.
- The string could contain all repeating characters.
Intuition
A brute-force approach would involve checking each character in the string to see if it appears anywhere else. This would require nested loops, resulting in a time complexity of O(n^2), which is inefficient for large strings.
The key insight is that we can use a hash table (dictionary) to count the occurrences of each character in a single pass through the string. Then, in a second pass, we can find the first character with a count of 1. This approach reduces the time complexity to O(n), where n is the length of the string.
Approach
- Initialize a dictionary to store the frequency of each character.
- First Pass (Counting):
- Iterate through each character in the string.
- For each character, update its count in the dictionary.
- Second Pass (Finding the First Unique Character):
- Iterate through the string again.
- Return the index of the first character with a count of 1 in the dictionary.
- If no unique character is found, return
-1.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We make two passes over the string: one for counting and one for finding the first unique character.
- Space Complexity: O(1) in terms of the number of keys in the dictionary, since there are at most 26 lowercase English letters.
Solution
def firstUniqChar(s):
# Step 1: Initialize a dictionary to store character counts
char_count = {}
# Step 2: First pass - count occurrences of each character
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
# Step 3: Second pass - find the first unique character
for index, char in enumerate(s):
if char_count[char] == 1:
return index
# Step 4: If no unique character is found, return -1
return -1
Edge Cases Handled
- All characters are repeating: The function will correctly return
-1since no character has a count of 1. - Single character string: If the string contains only one character, it will be counted as unique and its index (0) will be returned.
- String with multiple unique characters: The function will return the index of the first unique character encountered in the second pass.