Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile.
For example, the strings
WORLD can be shuffled to form
HEWORLLLDO, or perhaps simply
It is not a shuffle if the original order of letters is not preserved. For example, the
WORLD cannot ever appear before the
R after being shuffled. This means that
EHLLOWRDLO, for instance, is not a shuffle of
WORLD, even though it contains all the original letters.
A string is a shuffle of twins if it can be formed by shuffling two identical strings. For example,
ABACBDECDE is a shuffle of twins because it can be formed by shuffling
DBEACBCADE is not a shuffle of twins because it cannot be formed by shuffling two identical strings.
Given an input string, output
0 if it is not a shuffle of twins, and output one of the twin strings if it is a shuffle of twins.
You may assume that the input string has a length inclusively between four and twenty characters and is composed entirely of uppercase alphabetic characters. It should be able to run in a reasonable amount of time, say, under 10 minutes.
This is code golf, so the shortest solution wins.
> ABACBDECDE ABCDE > DBEACBCADE 0 > FFFFFF FFF > FFGGG 0 > ABBA 0 > AABB AB > AABAAB AAB
I have an example (non-golfed) implementation.