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 :
Time complexity: O(N)
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