Given a string, find the first character which is non-repetitive

Eg : Input : teeterson      
     Output : r, as it is the first element which 
                        is non repetitive.

Solution 1 :

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of 
each character, if you find an element who's count is 1, return it.

Time Complexity : O(2N)= O(N)
Space Complexity : O(N)

Solution 2 :

To reduce Time for searching , we can use Hashmap.
Benefit from previous solution:
to get count for 2,3 etc we can easily use this function with little modification
To search for count 1, no need to iterate array again.

map < int , character > m;
map < int , character > : iterator it;
void *getNonRepChar(char *str)
{
    int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
    int i;
    for (i = 0; *(str+i);  i++){
       count[*(str+i)]++;
       m.insert(make_pair(count,*(str+i)));
    }//for ended
  return count;
}//function ended

 it.find(1);
 if(it != end() ){
   // element found
   character op = it->second ; 
   printd (" %c has count %d" ,op,1); 
  }
 else  
 printf ("Not found Such element");

Time Complexity : O(N)
Space Complexity : O(N)

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE