Parent string of two given strings

Question

Given 2 strings, we have to find a string smallest in length such that the given strings are subsequences to the string. In other words, we need to find a string such that deleting some characters result in the given strings. was thinking of brute force and LCS, but in vain.

12345 and 11234 should result in 112345 WWA and WWS have a answer WWAS

LCS is pretty memory inefficient ( the DP one ) and brute force is just childish. What should I do?

Answer 1

Perhaps you could do a global alignment with Needleman-Wunsch and a high mismatch penalty, to prefer indels. At the end, merge the alignment into a "parent string" by taking letters from matching positions, and then a letter from either of the inserted letters, e.g.:

WW-A
||  
WWS-

WWSA

Or:

-12345
 ||||
11234-

112345

Memory is O(nm), but a modification narrows that down to O(min(n,m)).

Answer 2

There's a well defined algorithm in standard library which would serve your purpose.

set_union ();

Condition is your input ranges must be sorted.