problem : https://www.codechef.com/problems/KOL1510

my solution : https://ideone.com/Qyaw2Y

I am trying to find the shortest common supersequence for all the strings… whats wrong in this approach?? i am getting wrong answer

problem : https://www.codechef.com/problems/KOL1510

my solution : https://ideone.com/Qyaw2Y

I am trying to find the shortest common supersequence for all the strings… whats wrong in this approach?? i am getting wrong answer

Input:

`1 3 B G GB`

Correct output is `GB`

.

Your code constructs `BG`

from the first 2 and then `BGB`

from `BG`

and `GB`

, which is incorrect.

3 Likes

so if i sort the strings according to size and construct the solution using the largest words first… will it work??

It did’nt… well can u suggest any modification i need to do in my solution?? or should i go with the editorial?? thanks in advance

An approach like this will not work for sure. That’s because the shortest common supersequence problem for more than two strings is NP-Complete (according to Wikipedia). So you should take a look at the editorial