Whats Wrong in this approach for the question KOL1510 ?

problem : KOL1510 Problem - CodeChef

my solution : Qyaw2Y - Online C++0x Compiler & Debugging Tool - Ideone.com

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

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 :slight_smile: