Saturday, January 18, 2014

Find first non repeating character in a string

You are given a string, find its first non-repeating character?

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.

Code :
#include<stdlib.h>
#include<stdio.h>
#define NO_OF_CHARS 256

/* The function returns index of first non-repeating
   character in a string */
int getFirstNonRepeating(char *str)
{
 int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
 int i;
 for (i = 0; *(str+i);  i++)
   count[*(str+i)]++;
 int index = -1;

 for (i = 0; *(str+i);  i++)
 {
  if(count[*(str+i)] == 1)
  {
    index = i;
    break;
  }
 }
 return index;
}

Time complexity: O(N)

0 comments:

Post a Comment