rowang rowang - 2 months ago 17
C++ Question

First unique character in string using Unordered_map c++

I am trying to find the first unique character of a string using unordered_map in c++. LeetCodeProblem My code:

int firstUniqChar(string s) {
unordered_map<char,int> m;
for(int i=0;i<s.length();i++){
m[s[i]]++;
}
unordered_map<char,int>::iterator mit;
for(mit=m.begin();mit!=m.end();mit++){
if(mit->second ==1)
for(int i=0;i<s.length();i++){
if(mit->first == s[i])
return i;
}
}
return -1;
}


The output is not correct.
If I try to debug it in eclipse it says could not resolve unordered_map. I could not find the bug in my code. Please help me in understanding the bug.

Answer

unordered_map doesn't ensure that the elements are stored in the order you've inserted. So when you are iterating over it, there is no guarantee that the first element for which second is 1 is necessarily the first unique character.

You should iterate over the string instead:

int firstUniqChar(string s) {
    unordered_map<char,int> m;
    for(int i=0;i<s.length();i++){
        m[s[i]]++;
    }

    for (int i = 0; i < s.length(); i++){
      if (m[s[i]] == 1) {
        return i;
      }
    }
    return -1;
}