take two integer arrays A and B of size 26 ,A is for storing count and
B is for index .Initialize both the array with 0's. Then iterate
through the string once and keep incrementing the respective character
count in A and store the character index in B. Now in array B find
the minimum index whose count in A is 1.
Time Complexity : O(n)
code:
#include <stdio.h>
#include <string.h>
int main()
{
int i=0, min=1000000;
char c;
char a[26],b[26];
char s[100];
scanf("%s",s);
for( i=0;i<26;i++)
{
a[i]=0;
b[i]=0;
}
for( i=0;i<strlen(s);i++)
{
a[s[i]-97]++;
b[s[i]-97]=i;
}
for(i=0;i<26;i++)
{
if(a[i]==1)
if(b[i]<min)
{
min=b[i];
c=i+97;
}
}
printf("\nFirst unrepeated character is %c",c);
return 0;
}
On 10/13/10, Asquare <anshika.sp...@gmail.com> wrote:
> Given a string,find the first un-repeated character in it?
> Im getting O(n2) or O(mn)
> Anyone with a solution of lower complexity..??
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
