Description: Given a string, find the first non-repeating character in it.

If video does not load, Click here

If the input string is “ipupil”, then output should be ‘u’ as ‘u’ is the first character that doesn’t appear again.

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

1) Create a character array ‘count’ containing 256 elements corresponding to possible characters in the string.

2) Initialize all elements of ‘count’ array to 0.

3)Scan through all elements of the string incrementing ‘count’ as follows:

 -count[string[i]]=count[string[i]] + 1

4)Scan through the string and stop when you encounter the first index ‘i’ for which:


5)Character present at index ‘i’ is the first non-repeating character. 


Input string: string = ipupil

  count['i'] = 2
  count['p'] = 2
  count['u'] = 1
  count['l'] = 1

Get the first character whose count is 1 ('u’').

Implementation using C:



#define NUMBER_CHARS 256


/* Returns an array containing count of characters in the passed char array */

int *getCharCount(char *string)


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

   int i;

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


   return count;



/* The function returns index of first non-repeatingcharacter in a string. If all characters are repeating then returns -1 */

int firstNonRep(char *string)


  int *count = getCharCount(string);

  int index = -1, i;




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


            index = i;






  return index;



/* Driver program to test input for above function */

int main()


  char string[] = "ipupil";

  int index =  firstNonRep(string);

  if (index == -1)

            printf("All characters are repeating");


   printf("First non-repeating character:%c", string[index]);


  return 0;


 Time Complexity:


Go to top