Every short-read assembler in current use — SPAdes, Velvet, MEGAHIT — is built on de Bruijn
graphs. Instead of comparing reads pairwise, you shatter them into k-mers and let the graph
structure encode the overlaps implicitly, which turns assembly from a quadratic comparison
problem into a graph traversal.
Statement
Given a collection of k-mers all of the same length k, build the de Bruijn graph. Each k-mer
becomes an edge from its (k-1)-length prefix to its (k-1)-length suffix.
The first line holds n, the number of k-mers; the next n lines hold them.
Print the adjacency list, one line per node that has outgoing edges, in this exact form:
PREFIX -> SUFFIX1,SUFFIX2
Sort the lines lexicographically by prefix, and within a line sort the suffixes lexicographically.
List each distinct suffix only once per prefix, so duplicate k-mers do not produce duplicate
entries.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
How many k-mers follow
1 <= n <= 100
|
kmers
line 2
|
list[str] |
The k-mers, one per line, all the same length
2 <= k <= 30, uppercase A, C, G, T only
|
These variables are already read for you in the starter code on the right.
Output
str one 'PREFIX -> SUFFIX1,SUFFIX2' line per node, sorted lexicographically
Sample Cases
8
ATG
TGG
TGC
GTG
GGC
GCA
GCG
CGT
AT -> TG
CG -> GT
GC -> CA,CG
GG -> GC
GT -> TG
TG -> GC,GG
2
AAA
AAA
AA -> AASubmit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= n <= 100- Every k-mer has the same length
k, with2 <= k <= 30 - Lines are sorted by prefix; suffixes within a line are sorted and de-duplicated
- Use
->(space, arrow, space) and comma-separated suffixes with no spaces
Further Reading
- The prefix of a k-mer is
kmer[:-1]and the suffix iskmer[1:]. - A
dictofsets handles the de-duplication; sort when you print.