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

 
If video does not load, Click here
 
Example:

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

Algorithm:
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:

count[string[i]]==1

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

Example:

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:
 

#include<stdlib.h>

#include<stdio.h>

#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++)

            count[*(string+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;

 i=0;

while(*(string+i)!=0)

{

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

            {

            index = i;

            break;

            } 

 i++;

  }

  free(count);

  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");

  else

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

  getchar();

  return 0;

}

 Time Complexity:

O(n)

Go to top