Minimum Genetic Mutation

A gene string has length 8 and consists of letters A/C/G/T. Given a start and end gene and a bank of allowed genes, return the minimum number of single-character mutations needed to transform start into end. If impossible, return -1.

Why this is worth learning

Generate neighbors by changing one character to one of the other three bases. The bank is an admissibility filter; being one mutation away is not enough unless the resulting gene is allowed.

Before coding: one-minute experiment

Why is start=end answered with 0 even for an empty bank, while a different absent target is answered with -1?

Function signature

func MinMutation(start, end string, bank []string) int

Inputs / outputs

• start, end: gene strings.
• bank: allowed intermediate genes.
• Return: minimum mutations, or -1 if unreachable.

Example

start = "AACCGGTT", end = "AACCGGTA"
bank = ["AACCGGTA"]
Output: 1

Constraints

• 0 <= len(bank) <= 10_000
• start, end, and every bank string have exactly 8 bytes, each one of A, C, G, T.

Core idea (near-solution)

Enumerating mutation sequences without remembering genes can revisit the same states indefinitely. A future continuation depends only on the current gene, so merge paths that reach it and keep its earliest distance. Generate one-position substitutions over A,C,G,T, admit only bank members, and use a FIFO queue because every mutation costs one. The starting gene is already a valid initial state: if it equals the goal, zero changes suffice even without a bank entry. For a different goal, an absent bank entry makes reaching it impossible.

Invariant: the first time a gene is visited in BFS, its distance is minimal.

Algorithm (step-by-step)

1. If start == end, return 0 before consulting the bank.
2. Build the bank set; if a different end is absent, return -1.
3. Enqueue (start,0) and mark start visited.
4. For each removed gene, return its distance if it equals end. Otherwise, for each of its eight positions, save the original byte and try each of the other three bases.
5. Enqueue an allowed, unseen candidate at distance+1 and mark it immediately. Restore the saved byte before moving to the next position.
6. Return -1 if the queue empties.

Correctness sketch

Every generated candidate differs at exactly one position because the original byte is restored before moving to the next position. Filtering by the bank yields exactly the permitted outgoing neighbors. FIFO exploration with marking on enqueue discovers each gene at its smallest mutation count. The initial gene has distance zero; if it already equals the target, no bank entry is needed. Otherwise reaching the target requires the target to be in the bank. Exhausting all reachable bank genes proves no allowed transformation sequence exists.

Trace (hand walkthrough)

Example input:
start = "AACCGGTT", end = "AACCGGTA"
bank = ["AACCGGTA"]
Output: 1

Walk:
- start AACCGGTT
- mutate last char T->A to match bank AACCGGTA
- reach end in 1 step

Pitfalls to avoid

• Generating neighbors without checking membership in the bank.
• Revisiting genes (causes exponential blowup).
• Forgetting to handle start == end (distance 0).

Debugging lens

Restore the modified position before generating changes at another position. Forgetting restoration creates edges that change two or more characters. Test absent targets, cycles, and disconnected bank components.

Complexity

For the fixed gene length 8 and alphabet size 4, expected time and extra space are O(B), where B is bank size. With variable length L and alphabet A, this Go implementation constructs/hashes each candidate string and takes O(B A L^2) expected time and O(B L) string storage.

Implementation notes (Go)

• Use a map[string]bool for visited.
• Represent the queue as a slice with a head index.

Reconstruction checkpoint

Evaluate start="AACCGGTT", end="AACCGGTT", bank=[]; then change end to "AACCGGTA" with the same empty bank. Why must the zero-change case precede a bank-membership rejection?

Return to Graph BFS · Module quiz