Overlap graphs are the foundation of overlap-layout-consensus assembly: each read becomes a node,
and an edge means two reads share enough sequence to be adjacent in the genome. Building one is
the first step of assemblers like Celera, and counting its edges tells you how tangled the
assembly problem is.
Statement
Given a collection of DNA strings, build the overlap graph for k = 3: draw a directed edge from
string s to string t (with s and t different entries) whenever the last 3 characters
of s exactly equal the first 3 characters of t.
The first line holds n, the number of sequences; the next n lines hold them.
Print a single integer: the number of directed edges in the graph.
Entries are compared by position, so two identical sequences at different positions may form
edges with each other. An entry never forms an edge with itself.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
How many sequences follow
1 <= n <= 50
|
sequences
line 2
|
list[str] |
The DNA sequences, one per line
each 3 <= length <= 100, uppercase A, C, G, T only
|
These variables are already read for you in the starter code on the right.
Output
int the number of directed edges in the k=3 overlap graph
Sample Cases
4
AAATAAA
AAATTTT
TTTTCCC
AAATCCC
32
ACGT
GTAC
0Submit 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 <= 50- Every sequence is at least 3 characters long
k = 3is fixed- No self-edges; distinct positions with identical sequences may still form edges
Further Reading
- Compare
s[-3:]witht[:3]for every ordered pair of distinct positions. - Remember to check both directions for each pair — the graph is directed.