Programming: Finding first non-repeating character in given string

Given a string, find the first non-repeating character in it. For example, if the input string is “HelloWorld”, then output should be ‘H’ and if input string is “HelloHowAreYou”, then output should be ‘w’.

We can use string characters as index and build a count array. Following is the algorithm.

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.

Example:

Input string: str = helloworld
1: Construct character count array from the input string.

  count['h'] = 1
  count['e'] = 1
  count['l'] = 3
  count['o'] = 2
  count['w'] = 1
  ……
2: Get the first character who's count is 1 ('h').

Implementation:

#include <iostream>

#include <malloc.h>

#define NO_OF_CHAR 256

using namespace std;



int *getcharcountarray(char *str)

{

    int *count = (int *)calloc(sizeof(int), NO_OF_CHAR);

    int i;

    for(i=0; *(str+i); i++)

     count[*(str+i)]++;

    return count;

}



int gettheindex(char *str)

{

    int *count = getcharcountarray(str);

    int index = -1, i;

    

    for(i=0; *(str+i); i++)

    {

     if(count[*(str+i)] == 1)

     {

         index = i;

         break;

     }

    }

    free(count);

    return index;

}



int main()

{

    char str[] = "samsungelectronics";

    int index = gettheindex(str);

    if(index == -1)

     cout<<"Either all characters are repeating or string is empty"<<endl;

    else

     cout<<"First repeating character is "<<str[index]<<endl;

    return 0;



}