433 · Minimum Genetic Mutation

Transfer test of Word Ladder with $|\Sigma| = 4$ nucleotides ({'A','C','G','T'}) and fixed length 8. Mutate characters, validate against gene bank, and remove from bank upon queue insertion to guarantee $O(1)$ cycle avoidance.

Execution Stage

idle

INVARIANT Genetic Mutation Invariant: Branching is $8 \times 3 = 24$ candidates per node. Removing valid mutations directly from bankSet prevents revisiting nodes and guarantees minimal mutation count on first arrival.

Mutations 0

Queue Size 0

Remaining Bank 0

Gene Bank 0 genes

Press Run to trace Minimum Genetic Mutation BFS.

0 / 0

Speed

Java · Reference Algorithm

INTERVIEW SCRIPT

How to Present Minimum Genetic Mutation to an Interviewer

1. The Transfer Test

"This is Word Ladder (LC 127) with a smaller alphabet: $|\Sigma| = 4$ for nucleotides ('A','C','G','T') and fixed length $L = 8$."

2. Bank Set Pruning

"Instead of a separate visited hash set, we remove matching genes directly from bankSet upon enqueuing: bankSet.remove(next)."

3. Return Metric: Edges vs Nodes

"Word Ladder counts vertices in sequence ($steps + 1$). Genetic Mutation counts transition moves ($steps$), returning 0 if start equals end."

4. Complexity Bound

"Each gene generates $8 \times 3 = 24$ mutations. With bank size $B \le 10$, BFS visits at most $B$ nodes in $O(B)$ time — near instantaneous."