# 387 First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note:You may assume the string contain only lowercase letters.
Idea:
• Map the frequencies of characters along with their position. Iterate through the hash table to the end, searching for the lowest index position, that also have a frequency == 1.
int firstUniqChar(string s)
{
// char -> position, frequency
unordered_map<char, pair<int, int>> freq_map;
freq_map.reserve(s.length());
for (int i = 0; i < s.length(); i++) {
if (freq_map.find(s[i]) != freq_map.end()) {
freq_map[s[i]].second++;
}
else freq_map.insert({ s[i], {i, 1} });
}
int index = INT_MAX;
for (auto i : freq_map) {
if (i.second.first < index && i.second.second == 1) {
index = i.second.first;
}
}
return index == INT_MAX ? -1 : index;
}
int main()
{
cout << firstUniqChar("leetcode") << endl;
cout << firstUniqChar("loveleetcode") << endl;
cout << firstUniqChar("ddaann") << endl;
}
Just for fun. Now the question in reverse. Find the first reoccurring character.
from collections import Counter
def firstReoccuringChar(s):
"""
:type s: str
:rtype: int
"""
char_freq = Counter()
for char in s:
if char in char_freq:
return char
else:
char_freq[char] += 1
return None
print(firstReoccuringChar('leetcode'))
Last modified 4yr ago