# efficient way to check the duplicate characters from string2 in string1

Discussion in 'C' started by cimon, Oct 17, 2008.

1. ### cimonNew Member

Joined:
Feb 9, 2007
Messages:
20
0
Trophy Points:
0
Is there any other efficient manner of checking duplicate characters from string2 in string1
Code:
```     char st1="mikem";
char st2="Tame";
int l1=strlen(st1);
int l2=strlen(st2);
int i,j;

for( i=0;i<strlen(st2);i++)
{

for( j=0;j<l1;j++)
{   if(st1[j]=='\0')
continue;

if(st2[i]==st1[j])
{
st1[j]='\0';
}
}
}```
The above is checking each and every alphabet from st2 and replacing it with null in st1 ,if match is found

Is ther Any other more efficient way , rather than this one

-thank you

Last edited by a moderator: Oct 17, 2008
2. ### oogaboogaNew Member

Joined:
Jan 9, 2008
Messages:
115
11
Trophy Points:
0
3. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
The algorithm you've presented operates in a time proportional to the lengths of the strings multiplied together, which might be O(n^2) (I don't know a lot about O() representation so that could be way off).
What you could do to improve matters is to run through the first string storing the number of times a particular character has occurred in a 26-number array (storing either the count or just whether or not a letter has been encountered, whichever is more relevant). Then just loop through the second string checking the array if that letter has been encountered.
Code:
```	int i,flags;
for (i=0; i<26; flags[i++]=0) ;
char *str1="Hello";
char *str2="World";
for (i=0; str1[i]; i++)
if (str1[i]>='a' && str1[i]<='z') flags[str1[i]-'a']=1;
for (i=0; str2[i]; i++)
if (str2[i]>='a' && str2[i]<='z' && flags[str2[i]-'a'])
putchar(str2[i]);
```
This should operate in O(n) time (if I'm correct about O() theory) because it operates in a time proportional to the lengths of the strings added together.
Output of the above is "ol".

4. ### oogaboogaNew Member

Joined:
Jan 9, 2008
Messages:
115
11
Trophy Points:
0
Very nice! That would be hard to beat.
Using tolower() will deal with uppercase letters as well.
Code:
```int i, n, flags;
char *str1="Hello";
char *str2="World";
for (i=0; i<26; flags[i++]=0)
;
for (i=0; str1[i]; i++) {
n = tolower(str1[i]) - 'a';
if (n >= 0 && n < 26)
flags[n] = 1;
}
for (i=0; str2[i]; i++) {
n = tolower(str2[i]) - 'a';
if (n >= 0 && n < 26 && flags[n])
putchar(str2[i]);
}```

Joined:
Feb 9, 2007
Messages:
20