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


Given a string, find the first element which is non -repetitive i.e that element must not be present anywhere else in the string.


With two different solutions.
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
Labels: , , , ,