Minimum Genetic Mutation

Problem

A gene string is 8 characters long, each from {'A', 'C', 'G', 'T'}. A mutation changes exactly one character to one of the other three. You’re given a startGene, an endGene, and a bank of valid gene strings.

Return the minimum number of mutations to transform startGene into endGene, where every intermediate gene (after each single mutation) must be present in bank. If endGene is unreachable under these rules, return -1.

Note: startGene itself need not be in bank, but endGene must be (otherwise it’s unreachable).

Examples

• start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"] → 1 — one mutation at the last position.
• start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"] → 3 — path AACCGGTT → AACCGGTA → AACCGCTA → AAACGGTA… (any valid 3-step chain).
• start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"] → 3.
• start = "AACCGGTT", end = "AACCGGTA", bank = [] → -1 — end not in bank, no path.

Constraints

• len(startGene) == len(endGene) == 8; characters from {A, C, G, T}.
• 0 <= len(bank) <= 10; each bank string has length 8.

Think about it first

TL;DR

Shortest path in an unweighted graph of genes → BFS, counting levels until end appears. O(N · L · 4) time with N bank genes of length L.

Approach 1 — Brute-force DFS over all paths

The naive idea: recursively try every sequence of valid mutations, tracking depth, and take the minimum that reaches end. It’s correct but explores paths that BFS would prune, and it computes a minimum over an unweighted graph the hard way.

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        bank_set = set(bank)
        best = [float("inf")]

        def differ_by_one(a: str, b: str) -> bool:
            return sum(x != y for x, y in zip(a, b)) == 1

        def dfs(gene: str, steps: int, used: set) -> None:
            if gene == endGene:
                best[0] = min(best[0], steps)
                return
            for nxt in bank_set:
                if nxt not in used and differ_by_one(gene, nxt):
                    used.add(nxt)
                    dfs(nxt, steps + 1, used)
                    used.remove(nxt)

        dfs(startGene, 0, set())
        return best[0] if best[0] != float("inf") else -1

Complexity: worst case explores permutations of the bank → up to O(N!) paths. With N ≤ 10 it happens to survive, but it’s the wrong tool: shortest path on an unweighted graph is a BFS problem, and BFS finds the answer in one level-order sweep.

Approach 2 — BFS shortest path (the right tool)

The insight: valid genes are nodes; an edge connects two genes differing in exactly one character. Each mutation is one edge, all edges cost 1, so the fewest mutations is the shortest path — and BFS explores the graph in order of distance, so the level at which end is first dequeued is the minimum. A visited set prevents cycles. To find neighbors, generate all 24 one-character mutations of the current gene and keep those in the bank.

from collections import deque


class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        bank_set = set(bank)
        if endGene not in bank_set:
            return -1

        queue = deque([(startGene, 0)])
        visited = {startGene}
        choices = "ACGT"

        while queue:
            gene, steps = queue.popleft()
            if gene == endGene:
                return steps
            for i in range(len(gene)):
                for ch in choices:
                    if ch == gene[i]:
                        continue
                    mutated = gene[:i] + ch + gene[i + 1:]
                    if mutated in bank_set and mutated not in visited:
                        visited.add(mutated)
                        queue.append((mutated, steps + 1))
        return -1

Walkthrough (start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]):

• Level 0: AACCGGTT. Mutating each position, only AACCGGTA (last char T→A) is in the bank → enqueue at step 1.
• Level 1: AACCGGTA. One-char neighbors in bank: AACCGCTA (pos 5 G→C) → enqueue at step 2.
• Level 2: AACCGCTA → neighbor AAACGGTA? They differ in more than one spot along this exact chain, but BFS continues exploring all step-2 nodes until AAACGGTA is reached at step 3.
• First time end is dequeued, steps = 3 → return 3.

Complexity: each of ≤ N+1 genes generates L · 3 candidates (L = 8) and does an O(L) set lookup → O(N · L² ) overall, effectively constant here (N ≤ 10, L = 8). Space O(N) for visited and the queue.

Approach 3 — Bidirectional BFS

The insight: search from both start and end simultaneously, expanding whichever frontier is smaller each round; when the frontiers meet, you’ve found the shortest path. This roughly halves the explored depth — negligible on a 10-gene bank, but the canonical optimization for large word-ladder / gene graphs where a single-sided BFS frontier explodes exponentially. Prefer plain BFS for tiny inputs (simpler, no bug surface); reach for bidirectional BFS when the branching factor and depth are large.

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        bank_set = set(bank)
        if endGene not in bank_set:
            return -1

        front, back = {startGene}, {endGene}
        seen = {startGene, endGene}
        choices = "ACGT"
        steps = 0

        while front and back:
            if len(front) > len(back):
                front, back = back, front          # expand the smaller frontier
            steps += 1
            nxt_front = set()
            for gene in front:
                for i in range(len(gene)):
                    for ch in choices:
                        if ch == gene[i]:
                            continue
                        mutated = gene[:i] + ch + gene[i + 1:]
                        if mutated in back:
                            return steps            # frontiers meet
                        if mutated in bank_set and mutated not in seen:
                            seen.add(mutated)
                            nxt_front.add(mutated)
            front = nxt_front
        return -1

Walkthrough (start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]): front = {start}, back = {end}. Step 1: mutating AACCGGTT produces AACCGGTA, which is in back → return 1.

Complexity: same asymptotic class but explores ~O(b^(d/2)) instead of O(b^d) nodes (b = branching, d = depth) — a large practical win on big graphs. Space O(N).

Common pitfalls

• Returning 0 or a wrong count when start == end: BFS handles it (dequeues end at step 0), but the early endGene not in bank_set guard would wrongly return -1 if start == end and it’s not in the bank — check start == end first if the problem allows it (LeetCode’s tests treat end as needing to be in bank).
• Counting nodes visited instead of edges/levels — the answer is the number of mutations (edges), which is the BFS level.
• Forgetting the visited set, causing revisits and, in DFS, exponential blowup or infinite loops.
• Using DFS and returning the first path found rather than the shortest — DFS’s first hit is not guaranteed minimal on an unweighted graph.

Pattern takeaway

“Fewest one-step transformations from A to B, given a set of legal intermediates” is shortest path on an unweighted graph — always BFS, where the first time you pop the target gives the minimum. Generate neighbors by the problem’s move rule (one-character mutations here). When the graph is huge, bidirectional BFS meeting in the middle is the standard speedup; DFS is the wrong tool because its first solution isn’t the shortest.