Minimum Genetic Mutation
Minimum Genetic Mutation: find the minimum number of single-gene mutations to turn startGene into endGene, only passing through genes in bank.
- 0 <= bank.length <= 10
- startGene.length == endGene.length == bank[i].length == 8
- startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].
Intuition
Minimum genetic mutation counts the fewest single-character changes turning one gene string into another, where every intermediate must appear in the given bank. That constraint is what makes it a graph problem rather than a string-distance one. Edit distance would count changes between two strings directly, but it has no notion of legal intermediates. Here the path matters: each step must land on a gene in the bank, so the genes form a graph where an edge joins two genes differing by exactly one character. Shortest path on an unweighted graph is BFS, and this is Word Ladder with a smaller alphabet: - Generate neighbours on demand by substituting each of A, C, G, T at each position, keeping only candidates present in the bank. With gene strings of length 8 and four letters, that is 32 candidates per gene — far cheaper than comparing every pair in the bank to build a graph explicitly. BFS explores in layers of equal mutation count, so the first time the target is generated, that count is minimal. Return immediately. Two guards matter. Check up front whether the end gene is in the bank at all — if not it is unreachable, so return −1. And remove each gene from the bank as it is enqueued, which serves as the visited marker and prevents the same gene being explored from several directions. The count starts at 0, since the problem counts mutations rather than genes visited — the opposite of Word Ladder, which starts at 1.
Word Ladder with a four-letter alphabet — ACGT instead of a–z, and a bank instead of a word list. Recognising the two problems as identical means the second one costs no new thinking, only a change of constants.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(n * L * 4) time and O(n * L) space.
See why edit distance does not apply
Edit distance counts differences between two strings directly but ignores whether intermediates are legal. Here every step must land on a gene in the bank, which makes this a shortest-path problem on a graph.
Check the target is in the bank
If the end gene is absent, no legal mutation sequence can reach it — return −1 immediately. This guard costs one lookup and avoids a full fruitless search.
Generate neighbours over four letters
For each position, substitute A, C, G and T, skipping the existing letter. That is 32 candidates for a length-8 gene, far cheaper than comparing every pair in the bank to build a graph.
Remove genes as they are enqueued
Delete each gene from the bank when it enters the queue. This doubles as the visited marker and stops the same gene being reached from several directions, which would otherwise multiply the search.
Return at the first sighting of the target
BFS explores in layers of equal mutation count, so the first generation of the end gene is the minimum. Return at once rather than finishing the level.
Count mutations, not genes
The counter starts at 0, since the problem asks for the number of changes. Word Ladder starts at 1 because it counts words in the sequence — the two differ by exactly this off-by-one.
Cost of the search
Each of the n bank genes generates 4 × L candidates checked in O(1), giving O(n · L) time with a small constant, and O(n · L) space for the bank set and queue.
Solution & live demo
Common pitfalls
Allowing the unchanged character
for ch in 'ACGT':
cand = gene[:i] + ch + gene[i+1:]if ch == gene[i]:
continueSubstituting a character with itself produces the current gene, which is already visited — harmless with a visited check, but it wastes a set lookup on every position and obscures that a mutation must actually change something.
Counting the start gene as a mutation
q = deque([(startGene, 1)])
q = deque([(startGene, 0)])
The answer counts mutations, not genes visited — reaching the start requires zero. Unlike Word Ladder, which counts words in the sequence, this one starts at 0.
Not checking the bank membership of the target
q = deque([(startGene, 0)])
if endGene not in bankSet:
return -1Every intermediate gene must be in the bank, including the final one. Without the check the BFS exhausts the reachable set before concluding, and the intent is less obvious.
Edge cases
Return -1 without running BFS.
Not a real test case per constraints, but would need 0 mutations.
Never generated as neighbors, simply ignored.
BFS exhausts the queue without reaching endGene; return -1.