DSA problem
Minimum Genetic Mutation
A gene string can be represented by an 8-character string with characters from the set {'A', 'C', 'G', 'T'}. Given two gene strings startGene and endGene and a gene bank, return the minimum number of mutations needed to mutate from startGene to endGene. A mutation changes exactly one character; every intermediate gene must be in the bank. If there is no such mutation path, return -1.
This is a shortest-path problem on an implicit graph: each node is an 8-character gene string in the bank (plus the start gene), and there is an undirected edge between any two genes that differ by exactly one character. We want the shortest unweighted path from startGene to endGene.
Because all edges have unit weight, BFS finds the shortest path optimally. We push startGene with distance 0, expand level by level, and at each step generate every neighbour by changing one of the 8 positions to each of the 3 other letters. We only enqueue a neighbour if it is present in the bank and has not been visited yet.
The total work is bounded by the bank size B: we examine each gene at most once, and for each we generate 8 * 3 = 24 candidate neighbours. The complexity is therefore O(B) time and O(B) space, treating the constant gene length of 8 as a literal constant.
Examples
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]1startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]2startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]3Constraints
- 0 <= bank.length <= 10
- startGene.length == endGene.length
- startGene.length == bank[i].length
- startGene.length == 8
- startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.