Problem
Find the first non repeating character in a given string. You may assume that the string contains any character from any language in the world, for e.g. an Arabic
or Greek character even.
Solution
#include <iostream>
#include <iomanip>
#include <hash_map>
#include <string>
#include <algorithm>
using namespace std;
using namespace stdext;
bool FindFirstNonRepeatChar(wstring str, wchar_t& output)
{
hash_map<wchar_t, int> hm;
typedef pair <wchar_t, int> Char_Int_Pair;
for(wstring::iterator it = str.begin(); it != str.end(); ++it){
if(hm.find(*it) != hm.end()){
hm[*it] ++;
}
else{
hm[*it] = 1;
}
}
for(hash_map<wchar_t, int>::iterator it = hm.begin(); it != hm.end(); ++it){
if(it->second < 2){
output = it->first;
return true;
}
}
return false;
}
void Display(std::wstring const& text)
{
for(wstring::const_iterator it = text.begin(); it != text.end(); ++it){
if(*it < 0x80){
wcout << *it;
}
else{
wcout.fill(L'0');
wcout << "\\u" << hex << setw(4) << (long)*it;
}
}
wcout << endl;
}
int main(int argc, char* argv[])
{
wstring testCases[] = {
L"mmaab",
L"aabbc",
L"a",
L"",
L"bbcc",
L"Hello",
L"иПривет",
L"λληνικά -- Español.",
};
for(int i = 0; i < sizeof(testCases) /sizeof(testCases[0]); ++ i){
wchar_t output;
Display(testCases[i]);
bool found = FindFirstNonRepeatChar(testCases[i], output);
if(found){
wcout << L"The first non repeated char is ";
wcout.fill(L'0');
wcout << "\\u" << hex << setw(4) << (long)output;
if(output < 0x80){
wcout << "--'" << output << "'";
}
}
else{
wcout << L"Sorry, None is found" << endl;
}
wcout << endl << endl;
}
return 0;
}
Output
mmaab
The first non repeated char is \u0062--'b'
aabbc
The first non repeated char is \u0063--'c'
a
The first non repeated char is \u0061--'a'
Sorry, None is found
bbcc
Sorry, None is found
Hello
The first non repeated char is \u0048--'H'
\u0438\u041f\u0440\u0438\u0432\u0435\u0442
The first non repeated char is \u0440
\u03bb\u03bb\u03b7\u03bd\u03b9\u03ba\u03ac -- Espa\u00f1ol.
The first non repeated char is \u03b7
Press any key to continue . . .