First Non-Repeating Character
Implement a function to find the first non-repeating character in a string and return its index. If no such character exists, return -1.
Examples:
Example 1:
Input: s = "leetcode"
Output: 0 (character 'l')
Example 2:
Input: s = "loveleetcode"
Output: 2 (character 'v')
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
1 <= s.length <= 105scontains only lowercase English letters.
Function Signature (Python):
class Solution:
def firstUniqChar(self, s: str) -> int:
# Your code here
pass
Related Python Concepts
collections.Counter enumerate() Time Complexity Space Complexity Edge CasesHint
This problem usually involves two main steps:
- Counting Frequencies: How can you efficiently count how many times each character appears in the string?
- A hash map (dictionary) is a good choice for storing character counts.
- Finding the First Unique: Once you have the counts, how do you find the first character in the original string that has a count of 1?
- You'll likely need to iterate through the string again, in its original order.
- Edge Cases: What if the string is empty (constraint says
s.length >= 1, but good to think about)? What if all characters repeat?
Solution Explanation & Interview Strategy
The Goal: We need to look at a string (e.g., "loveleetcode") and find the very first character that appears only once. For "loveleetcode", 'l' appears twice, 'o' twice, 'v' once. Since 'v' is the first one we encounter that's unique, we return its position (index 2).
If every character repeats (like in "aabbcc"), there's no unique character, so we'd return -1.
Approach 1: Hash Map for Frequencies, then Re-iterate String (Two-Pass)
This is a common and intuitive approach.
- First Pass (Count Frequencies): Iterate through the string once to build a frequency map (a dictionary or hash map) where keys are characters and values are their counts.
- Second Pass (Find First Unique): Iterate through the string again from the beginning. For each character, check its count in the frequency map. The first character encountered that has a count of 1 is our answer. Return its index.
class Solution:
def firstUniqChar_hash_map(self, s: str) -> int:
char_counts = {}
# First pass: build frequency map
for char in s:
char_counts[char] = char_counts.get(char, 0) + 1
# Second pass: find the first character with count 1
for index, char in enumerate(s):
if char_counts[char] == 1:
return index
return -1 # No unique character found
# Example Usage:
# sol = Solution()
# print(sol.firstUniqChar_hash_map("leetcode")) # Output: 0
# print(sol.firstUniqChar_hash_map("loveleetcode")) # Output: 2
# print(sol.firstUniqChar_hash_map("aabb")) # Output: -1
- First Pass (Counting):
char_countsbecomes:{'l': 2, 'o': 2, 'v': 1, 'e': 3, 't': 1, 'c': 1, 'd': 1}
- Second Pass (Finding):
index = 0, char = 'l'.char_counts['l']is 2. Continue.index = 1, char = 'o'.char_counts['o']is 2. Continue.index = 2, char = 'v'.char_counts['v']is 1. Returnindex(which is 2).
Complexity Analysis:
Time Complexity: O(N), where N is the length of the string. We iterate through the string twice (once to build the map, once to find the unique character). O(N) + O(N) = O(N).
Space Complexity: O(K), where K is the number of unique characters in the string (or the size of the character set, e.g., 26 for lowercase English letters if K is bounded). In the worst case, if all characters are unique, K can be N, so it's O(N). More precisely, it's O(min(N, C)) where C is the size of the character set.
Approach 2: Using `collections.Counter` (Pythonic Two-Pass)
Python's collections.Counter is a specialized dictionary subclass for counting hashable objects. It simplifies the frequency counting step.
import collections
class Solution:
def firstUniqChar_counter(self, s: str) -> int:
# First pass: build frequency map using Counter
char_counts = collections.Counter(s)
# Second pass: find the first character with count 1
for index, char in enumerate(s):
if char_counts[char] == 1:
return index
return -1
# Example Usage:
# sol = Solution()
# print(sol.firstUniqChar_counter("loveleetcode")) # Output: 2
Complexity Analysis:
Time Complexity: O(N). collections.Counter(s) takes O(N) time. The second pass is also O(N).
Space Complexity: O(K) or O(min(N,C)), same as the manual hash map approach, for storing the character counts.
Interview Note: Using collections.Counter is perfectly fine and often appreciated for its conciseness, as long as you understand that it's essentially doing the same work as a manual frequency count under the hood.
Key Takeaways for Interviews:
- Two-Pass Strategy: Clearly articulate the two-pass approach (count, then find). This is the standard way to solve this.
- Frequency Counting: Explain the use of a hash map (dictionary) for efficient frequency counting. Mentioning Python's
collections.Counteras a convenient tool is a plus. - Preserving Order: Emphasize that the second pass must iterate through the original string (or its indices) to find the first unique character in its original order. Iterating through the keys of the hash map would not guarantee finding the first one.
- Complexity: Be ready to discuss time and space complexity. The O(N) time and O(K) space (where K is number of unique chars or size of alphabet) is typical.
- Edge Cases: What if the string is empty? (Problem constraint says length >= 1). What if all characters repeat? (Return -1). What if all characters are unique? (Return 0).