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'))