LeetCode: First Unique Character in a String

Problem Statement

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Example

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contains only lowercase letters.

Solution Thought Process

This is a hash map problem. First, we count the frequency of the characters in the string by iterating over the string once. Then we iterate through the string again, this time if we find the frequency 1 of a character, we will set this as the answer and we break the loop. If no element's frequency which equals 1, we return -1 as the answer.

Solution

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> M;
        for(int i=0;i<s.size();i++)
        {
            if(M.count(s[i]))
            {
                M[s[i]]++;
            }
            else {
                M[s[i]] = 1;
            }
        }
        int answer_index = -1;
        for(int i=0;i<s.size();i++)
        {
            if(M[s[i]]==1)
            {
                answer_index = i;
                break;
            }
        }
        return answer_index;
    }
};

Complexity

Time Complexity: O(n), where n = length of s.

Space Complexity: O(n), where n = length of s.