
Description
Given a string s
, find the first non-repeating character in it and return its index. If it does not exist, return -1
. The problem asks for the position of the first character that appears exactly once in the string, considering its left-to-right order.
Intuition
To determine the first unique character, we need to count the occurrences of each character in the string. If a character appears only once, it is a candidate for being the "first unique character." The challenge is to efficiently keep track of character counts and then identify the first one with a count of 1.
Approach
- Counting Frequencies: We traverse the string and count how many times each character appears using a hash map (or dictionary).
- Identifying the Unique Character: After counting the frequencies, we iterate through the string again, checking the count of each character. The first character with a count of 1 is our answer.
- Returning the Index: Return the index of the first unique character. If no such character exists, return
-1
.
Steps:
- Create a hash map to store the frequency of each character.
- Iterate through the string to populate the hash map with character counts.
- Traverse the string again to find the first character with a count of 1 in the hash map.
- Return its index or
-1
if no such character exists.
Complexity
Time Complexity:
O(n), where n
is the length of the string. We perform two passes through the string: one for counting and one for identifying the first unique character.
Space Complexity:
O(1), because the hash map holds at most 26 key-value pairs (for lowercase English letters).
Code
C++
class Solution {
public:
int firstUniqChar(string s) {
unordered_map charCount;
// Count occurrences of each character
for (char c : s) {
charCount[c]++;
}
// Find the first character that occurs only once
for (int i = 0; i < s.size(); i++) {
if (charCount[s[i]] == 1) {
return i;
}
}
return -1;
}
};
Python
class Solution:
def firstUniqChar(self, s: str) -> int:
char_count = {}
# Count occurrences of each character
for c in s:
if c not in char_count:
char_count[c] = 0
char_count[c] += 1
# Find the first character that occurs only once
for i in range(len(s)):
if char_count[s[i]] == 1:
return i
return -1
Java
class Solution {
public int firstUniqChar(String s) {
Map charCount = new HashMap<>();
// Count occurrences of each character
for (char c : s.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// Find the first character that occurs only once
for (int i = 0; i < s.length(); i++) {
if (charCount.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
JavaScript
var firstUniqChar = function (s) {
s = s.split('')
let map = {}
for (let i of s) {
if (!map[i]) map[i] = 0
map[i] += 1
}
for (let i in s) {
if (map[s[i]] === 1) return i
}
return -1
};