Genome Sequencing – CodinGame solution in Python
First remove every subsequence that already appears inside another one, then try all permutations of the remaining strings (N ≤ 5, so at most 120 orders) and merge them left to right, each time overlapping the longest suffix of the current result with a prefix of the next string. The answer is the length of the shortest merged string over all orders.
The problem
You receive N DNA fragments (N up to 5, each up to 10 letters among A, C, G, T). The task is to find the length of the shortest sequence that contains every fragment as a contiguous substring.
Only the length is printed, not the sequence itself. This is the shortest common superstring problem, which is NP-hard in general, but the tiny input size makes an exhaustive search over orderings perfectly practical.
Approach, step by step
- Remove contained fragmentsIf one fragment is a substring of another (or a duplicate), it adds nothing to the answer. Deleting it up front is what makes the permutation search provably correct.
- Write a maximum-overlap mergemerge(a, b) returns a if b is already inside a; otherwise it finds the largest k such that the last k letters of a equal the first k letters of b, and returns a + b[k:]. Try k from min(len(a), len(b)) down to 0 and stop at the first match.
- Try every orderFor each permutation, fold the fragments with merge from left to right and measure the result. With N ≤ 5 that is at most 120 orders and a few hundred string comparisons each.
- Keep the minimum lengthPrint the smallest length found. You never need to store the strings themselves, only their lengths.
Complexity
O(N! · N · L²)O(N · L)120 permutations, up to 4 merges each, and each merge compares at most L prefixes of length ≤ L (merged strings stay under 50 characters). The whole thing runs in milliseconds.
Solution code
Bug fixed in this version: Python: nest() only looks for an overlap where the new fragment extends the current result to the left, and never checks whether the new fragment is already a substring of the result. Combined with no pre-filtering of contained fragments, this can overestimate. Found by comparing with an exhaustive search: for the fragments CACC, AC, CAAA the code prints 8, but CACCAAA (length 7) contains all three. The replacement removes contained fragments, merges with maximum overlap and was checked against brute force on 1,500 random cases.
Genome Sequencing – Python
from itertools import permutations
def merge(a, b):
"""Shortest string starting with a that contains b."""
if b in a:
return a
for k in range(min(len(a), len(b)), -1, -1):
if a.endswith(b[:k]):
return a + b[k:]
n = int(input())
subs = [input() for _ in range(n)]
# drop duplicates and strings already contained in another one
subs = [s for i, s in enumerate(subs)
if not any(s in t and (s != t or j < i) for j, t in enumerate(subs) if j != i)]
best = None
for order in permutations(subs):
res = order[0]
for s in order[1:]:
res = merge(res, s)
if best is None or len(res) < best:
best = len(res)
print(best)
Common mistakes
- Ignoring fragments contained in othersIf AC sits inside CACC, merging AC as a separate piece adds letters for nothing. The test set has fragments nested in others precisely to catch this.
- Greedy merging without trying all ordersRepeatedly merging the pair with the biggest overlap is the classic heuristic, but it is not always optimal. With N ≤ 5 there is no reason not to check all 120 orders.
- Taking the first overlap instead of the largestWhen searching the overlap, start from the longest possible length. Scanning from k = 0 upward and stopping at the first match gives zero overlap every time.
- Forgetting N = 1 and identical fragmentsA single fragment's answer is its own length, and duplicated fragments must count once. Deduplicating before the search handles both.
Going further
Why is 'remove contained strings, then try every order with maximum overlap' exact? Take any shortest superstring and look at where each remaining fragment starts in it. Because no fragment contains another, their start positions are all different and their end positions come in the same order, so the fragments appear in a definite left-to-right order. Between two consecutive fragments in that order, the optimal string can only do better by overlapping them as much as possible, so the optimum equals the max-overlap merge of that particular permutation. That is why the contained-fragment filter is not an optimisation but a correctness requirement: without it, two fragments can start at the same place or one can end before the previous one, and the argument, along with naive solutions, breaks down.
FAQ
Is brute force really acceptable for Genome Sequencing?
Yes. N is at most 5, so 120 permutations of strings under 10 characters is trivial. Smarter methods (bitmask DP over subsets) only matter for N around 15 or more.
Do I need to output the sequence itself?
No, only its length. Keeping the merged string is just the simplest way to measure it.
What if two fragments are identical?
Treat them as one. The contained-fragment filter should keep exactly one copy, otherwise both get removed as substrings of each other.