Dsa
Trees
Medium
The Genetic Sequence Match
A phylogenetic tree has nodes labeled with a single nucleotide (A, C, G, or T). A 'sequence' is formed by reading labels along any downward path (from a node to any of its descendants). Given a target sequence S, count how many distinct downward paths in the tree match S exactly.
Input Format:
Line 1: N (number of nodes)
Line 2: N characters (labels of nodes 0 to N-1)
Next N-1 lines: u v (u is parent of v)
Line N+1: S (target sequence string)
Example:
Input:
3
A A A
0 1
1 2
AA
Output:
2
Key concepts
depth-first searchstring matchingtree paths
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now