C++ 2 solutions

• Brute force solution, traverse string s 2 times. First time, store counts of every character into the hash table, second time, find the first character that appears only once.

``````class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> m;
for (auto &c : s) {
m[c]++;
}
for (int i = 0; i < s.size(); i++) {
if (m[s[i]] == 1) return i;
}
return -1;
}
};
``````

if the string is extremely long, we wouldn't want to traverse it twice, so instead only storing just counts of a char, we also store the index, and then traverse the hash table.

``````class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, pair<int, int>> m;
int idx = s.size();
for (int i = 0; i < s.size(); i++) {
m[s[i]].first++;
m[s[i]].second = i;
}
for (auto &p : m) {
if (p.second.first == 1) idx = min(idx, p.second.second);
}
return idx == s.size() ? -1 : idx;
}
};
``````

``````class Solution {
public:
int firstUniqChar(string s) {
std::pair<int, int> counts[26];

int n = s.size();
for (int i = 0; i < n; i++) {
int pos = s[i] - 'a';
counts[pos].first++;
counts[pos].second = i;
}

int index = n;

for (int i = 0; i < 26; i++) {
if (counts[i].first == 1) {
index = std::min(index, counts[i].second);
}
}

return (index == n) ? -1 : index;
}
};
``````

• @dr.pro If this is brute force, is there an optimal solution?

• This post is deleted!

• @dr.pro first solution worst complexity is 2N (N = s.size(), iterate string 2 times), second solution worst complexity is 2N + 26 (iterate string 1 time but every time 2 operations, plus iteration through hash map)?

• Another way to traverse the string only once.

You can use hashmap to store the index of non-duplicated numbers. For duplicates, save the index as INT_MAX. Return the minimum index.

``````
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> mymap;
int ans = INT_MAX;
for(int i = 0; i < s.size(); i++){
if(mymap.find(s[i]) == mymap.end()){
mymap[s[i]] = i;
}
else{
mymap[s[i]] = INT_MAX;
}
}
for(auto it : mymap){
ans = min(it.second, ans);
}
return (ans == INT_MAX)? -1 : ans;
}
};
``````

• class Solution {
public:
int firstUniqChar(string s) {

``````    int i;
vector<char> v(s.begin(),s.end());
for(i=0;i<v.size();i++)
{
char tmp=v[i];
v.erase(v.begin()+i);
if(find(v.begin(),v.end(),tmp)==v.end())
return i;
v.insert(v.begin()+i,tmp);

}
return -1;
}
``````

};
using vector its to simple

• @dr.pro I'm wondering for unordered_map, won't the elements go out of order? Then we won't be able to find the first character that appears only once.

• @sunfruit
`if(p.second.first == 1) idx = min(idx, p.second.second);` this solves the problem