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.

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

Core idea (near-solution)

Model genes as nodes in an unweighted graph, with edges between genes that differ by one character. BFS yields the shortest mutation path.

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

Algorithm (step-by-step)

1. Put all bank genes in a set for O(1) lookup.
2. If end is not in the set, return -1 (no valid path).
3. BFS from start:
   • For each gene, generate all single-character mutations (8 positions x 4 letters).
   • If a mutation is in the bank and unvisited, enqueue it with distance + 1.
4. Return the distance when end is reached; otherwise -1.

Correctness sketch

• Invariant: the first time a gene is visited in BFS, its distance is minimal.
• BFS explores nodes in increasing distance from the sources.
• The first time a node is visited is its shortest distance.
• Therefore the recorded distance/level is optimal.

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).

Complexity

• Time: O(8 * 4 * |bank|) in practice; BFS visits each gene once.
• Extra space: O(|bank|).

Implementation notes (Go)

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