10
Explanation
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 HELLO
and WORLD
can be shuffled to form HWEOLRLLOD
, or HEWORLLLDO
, or perhaps simply HELLOWORLD
.
It is not a shuffle if the original order of letters is not preserved. For example, the D
in WORLD
cannot ever appear before the R
after being shuffled. This means that EHLLOWRDLO
, for instance, is not a shuffle of HELLO
and 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 ABCDE
and ABCDE
. DBEACBCADE
is not a shuffle of twins because it cannot be formed by shuffling two identical strings.
Program Details
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.
Example I/O
> ABACBDECDE
ABCDE
> DBEACBCADE
0
> FFFFFF
FFF
> FFGGG
0
> ABBA
0
> AABB
AB
> AABAAB
AAB
I have an example (non-golfed) implementation.
Example string FGG violates assertion
that the input string has a length inclusively between four and twenty characters
, and don't tell me "never trust user input!", "never trust the specs!" – user unknown – 2011-12-02T15:59:49.827@userunknown That is so embarrassing! I edited it to
FFGGG
to make it consistent. – Peter Olson – 2011-12-02T16:07:36.8501Just out of curiosity, can anyone come up with a solution with sub-exponential worst case time complexity, or prove that there isn't any? – Ilmari Karonen – 2011-12-02T17:54:19.277