Construct a String Spelled by a Gapped Genome Path solved by 545

Gapped Genome Path String Problem

Reconstruct a string from a sequence of (k,d)-mers corresponding to a path in a paired de Bruijn graph.

Given: A sequence of (k, d)-mers (a₁|b₁), ... , (a_n|b_n) such that Suffix(a_i|b_i) = Prefix(a_i+1|b_i+1) for all i from 1 to n-1.

Return: A string Text where the i-th k-mer in Text is equal to Suffix(a_i|b_i) for all i from 1 to n, if such a string exists.

Sample Dataset

4 2
GACC|GCGC
ACCG|CGCC
CCGA|GCCG
CGAG|CCGG
GAGC|CGGA

Sample Output

GACCGAGCGCCGGA

Extra Dataset

Click for an extra dataset