#433 Minimum Genetic Mutation
the problem
In plain words
A gene is an 8-letter string over A, C, G and T. One mutation changes exactly one letter. You may only pass through genes listed in bank (the start gene doesn't need to be there, but the end gene does). Return the fewest mutations to turn startGene into endGene, or -1 if it can't be done.
in startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
out 1
Change the last T to A.
in startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
out 2
AACCGGTT → AACCGGTA → AAACGGTA.
- 0 ≤ bank.length ≤ 10
- startGene, endGene and bank[i] have length 8
- Only the letters A, C, G, T
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBFS shortest path (unweighted)
It's Word Ladder with a 4-letter alphabet: genes are vertices, one mutation is an edge, and "fewest mutations" is a BFS. Generate neighbours by trying the 3 other letters at each of the 8 positions.
solutions
From brute force to optimal
DFS through bank genes that are one letter apart, marking genes on the current chain; keep the shortest chain that reaches the end.
- From the current gene, try every unused bank gene that differs in exactly one position.
- Mark it, recurse, unmark.
- Prune chains already as long as the best.
In the worst case it explores every ordering of the B bank genes; each step compares strings of length L = 8.
The used flags and a recursion depth of at most B.
class Solution { private int best; /** Try every chain of one-letter mutations through the bank; keep the shortest. Exponential. */ public int minMutation(String startGene, String endGene, String[] bank) { best = Integer.MAX_VALUE; explore(startGene, endGene, bank, new boolean[bank.length], 0); return best == Integer.MAX_VALUE ? -1 : best; } private void explore(String gene, String end, String[] bank, boolean[] used, int steps) { if (steps >= best) return; // can't beat the best chain found so far if (gene.equals(end)) { best = steps; return; } for (int i = 0; i < bank.length; i++) { if (used[i] || !oneApart(gene, bank[i])) continue; used[i] = true; explore(bank[i], end, bank, used, steps + 1); used[i] = false; // undo: another chain may use this gene } } private boolean oneApart(String a, String b) { int diff = 0; for (int i = 0; i < a.length() && diff < 2; i++) if (a.charAt(i) != b.charAt(i)) diff++; return diff == 1; }}BFS from the start gene. For each gene, try 8 positions × 3 other letters; keep a candidate only if it's still in the unvisited bank set.
- unvisited = set(bank); if endGene isn't in it, return -1.
- BFS level by level; steps counts levels.
- For each polled gene: if it's endGene, return steps; else enqueue every one-letter mutation that
unvisited.remove(...)accepts.
Each of the ≤ B + 1 genes is expanded once: L positions × 3 letters, each building and hashing an L-letter string.
The set and the queue hold at most B genes of length L.
class Solution { /** Genes are vertices, one mutation is an edge: BFS from startGene gives the fewest mutations. */ public int minMutation(String startGene, String endGene, String[] bank) { Set<String> unvisited = new HashSet<>(Arrays.asList(bank)); if (!unvisited.contains(endGene)) return -1; // the target itself must be a valid gene char[] letters = {'A', 'C', 'G', 'T'}; Deque<String> queue = new ArrayDeque<>(List.of(startGene)); unvisited.remove(startGene); for (int steps = 0; !queue.isEmpty(); steps++) { for (int size = queue.size(); size > 0; size--) { // one BFS level = one more mutation String gene = queue.poll(); if (gene.equals(endGene)) return steps; char[] g = gene.toCharArray(); for (int i = 0; i < g.length; i++) { char original = g[i]; for (char ch : letters) { if (ch == original) continue; g[i] = ch; String next = new String(g); if (unvisited.remove(next)) queue.offer(next); // in the bank and new → visit it } g[i] = original; // undo before changing the next position } } } return -1; }}in the room
How to say it in the interview
talk track
- Say: "Shortest number of one-letter changes → BFS on an implicit graph, exactly like Word Ladder."
- Check that endGene is in the bank before anything else.
- Note the trade-off: generating 8 × 3 = 24 candidates per gene vs comparing every pair of bank genes — with a tiny bank both are fine; with a big one, generation wins.
traps
- Returning 0 or the wrong count when endGene isn't in the bank — it must be -1.
- Forgetting to restore the changed letter before trying the next position.
- Not removing a gene from the set when enqueuing it — the same gene gets queued many times.
what they ask next
Follow-ups
Return one shortest chain, not just its length?
Remember each gene's parent when it's first enqueued, then walk back from endGene.
Bank of 10⁵ genes?
Same BFS; it's O(B · L²). Bidirectional BFS (from both ends) cuts the explored set a lot in practice.
before you submit
Edge cases to test
- Empty bank → -1.
- endGene not in the bank → -1, even if it's one letter away.
- The bank contains the start gene — fine, just don't count it as a step.
- A chain that breaks halfway → -1.
practise next
Similar problems
- #127Word LadderHardin Graphs
- #909Snakes and LaddersMediumin Graphs
- #1197Minimum Knight MovesMediumin GraphsLeetCode Premium