Monday, May 9, 2011

WAP to Concatenating the Two String while removing duplicate characters Efficiently

Given two strings s1 and s2, s1 has some characters at the end which are same as some of s2's starting characters, so you have to concatenate the strings so that the repeated portion occurs only once.

ex: S1="ABCDEFGHIJK"
S2="GHIJKXYZ"

OUTPUT="ABCDEFGHIJKXYZ"


#include
#include
int main()
{
char s1[] ="ABCDEFGHIJK";//"ABCDCDEF";
char s2[]="GHIJKXYZ";// "CDEFGHI";
char s3[100];
char *p1;
char *p2;
p1= s1;
p2 =s2;
int i =0;
while(*p1 )
{
if(*p1 != *p2)
{
s3[i++] = *p1;
p1++;

}
if(*p1 == *p2)
{
s3[i++] = *p1;
p1++;
p2++;
}

}
while(*p2)
{
s3[i++] = *p2;
p2++;
}
s3[i] = '\0';
printf("string is %s",s3);
getchar();
}

Run Here https://ideone.com/Y1yGb

4 comments :

Unknown said...

Sir,

This algorithm of yours is not O(n), it is O(K*N)

Unknown said...

@sheetal..its O(n).where i K comes from..??

luffy said...

I think this code wont work.
take
s1=ABCDB
s2=BDG
result should be:ABCDBDG
According to code:ABCDBG

luffy said...

String concat(String s1,String s2)
{
String new;
int i;
for(i=s1.length-1;i>=0;i--)
if(s1.charAt(i)==s2[0])
break;
int k=0;
while(s1.charAt(i++)==s2.charAt(k++));
new=s1+s2.subString(k-1);
return new;
}