About Me

▼

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
at

4 comments:

  1. UnknownMay 10, 2011 at 3:41 AM

    Sir,

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

    ReplyDelete
  2. UnknownMay 13, 2011 at 1:31 PM

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

    ReplyDelete
  3. luffyMay 25, 2011 at 6:10 AM

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

    ReplyDelete
  4. luffyMay 25, 2011 at 6:22 AM

    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;
    }

    ReplyDelete

Hi thanks , we will get back to you shortly !!!