Problem
Write an efficient function to find the first non-repeated character in a string. For instance, the first nonrepeated character in “total” is ‘o’ and the first nonrepeated character in “teeter” is ‘r’. Discuss the efficiency of your algorithm.
Solution
First, build the character count hash map:
For each character If no value is stored for the character, store 1
Otherwise, increment the value
Second, scan the string:
For each character Return character if count in hash map is 1
If no characters have count 1, return null
#include <iostream>
#include <hash_map>
#include <string>
using namespace std;
using namespace stdext;
char first_nonrepeated_ch(string &s)
{
hash_map<char, int> h;
typedef pair <char, int> ci_pair;
hash_map<char, int>::iterator it;
char c;
for(int i = 0; i < s.length(); i ++){
c = s.at(i);
it = h.find(c);
if(it != h.end()){
it->second ++;
}
else{
h.insert(ci_pair(c, 1));
}
}
for(int i = 0; i < s.length(); i++){
c = s.at(i);
it = h.find(c);
if(it->second == 1){
return c;
}
}
return 0;
}
int main(int argc, char* argv[])
{
string str_list[5] = {"total", "eel", "hello", "hh", ""};
for(int i = 0; i< 5; i++){
cout << "The first non-repeated character in " << str_list[i] << " is " << first_nonrepeated_ch(str_list[i]) << endl;
}
return 0;
}
Output
The first non-repeated character in total is o
The first non-repeated character in eel is l
The first non-repeated character in hello is h
The first non-repeated character in hh is