C++ Solution with linear worst case complexity


  • 0
    U
    class Solution {
    public:
       
        int firstUniqChar(string s)
        {
            /* Character is used as the key, and a pair of integers for the value
               First integer is for the count and the second for the first index
            */ 
            unordered_map<char, pair<int,int> > myMap;
            pair<int,int> count_index;
            
            for(int i=0; i<s.length(); i++)
            {
                if (myMap.count(s[i]) == 0)
                {
                    (myMap[s[i]]).second = i;    
                }
                (myMap[s[i]]).first++;
            }
    
            for(int i=0; i<s.length(); i++)
            {
                count_index = myMap[s[i]];
                if (count_index.first == 1)
                {
                    return count_index.second;
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.