Minimum Genetic Mutation — InterviewPrepKit

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"] → 2 — change the last character (AACCGGTT → AACCGGTA, in bank), then position 2 (AACCGGTA → AAACGGTA, in bank).
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

Hint 1

Each valid gene is a node; two genes are connected by an edge if they differ in exactly one character. You want the shortest path (fewest edges) from start to end — a hallmark of BFS on an unweighted graph.

Hint 2

BFS level by level from start. The level index when you first pop end is the answer. Neighbors of a gene are the bank entries that differ from it in exactly one position (or, generate all 1-character mutations and keep those in the bank).

Hint 3

Because the alphabet is tiny (4 letters, 8 positions → 24 candidate mutations per gene) and the bank is small, either neighbor-finding works. Mark genes visited so you don't revisit. If BFS drains without reaching end, return -1.

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

Recursively try every sequence of valid mutations, track depth, and take the minimum depth that reaches end. It is correct but explores paths BFS would prune, and it computes a shortest path on an unweighted graph without exploiting that structure.

def minMutation(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 survives, but 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)

Valid genes are nodes, and an edge connects two genes differing in exactly one character. Each mutation is one edge and all edges cost 1, so the fewest mutations is the shortest path. 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


def minMutation(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, so enqueue it at step 1.
Level 1: AACCGGTA. Its one-char neighbors in the bank are AACCGCTA (pos 5 G→C) and AAACGGTA (pos 2 C→A). Enqueue both at step 2. AAACGGTA is end.
Level 2: AAACGGTA is dequeued and equals end, so return 2.

flowchart TD
    A["AACCGGTT (step 0)"] --> B["AACCGGTA (step 1)"]
    B --> C["AACCGCTA (step 2)"]
    B --> D["AAACGGTA = end (step 2)"]

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

Search from both start and end at once, expanding whichever frontier is smaller each round; when the frontiers meet, the shortest path is found. This roughly halves the explored depth. The gain is negligible on a 10-gene bank, but it is the standard optimization for large word-ladder or gene graphs where a single-sided BFS frontier grows exponentially. Prefer plain BFS for small inputs; use bidirectional BFS when the branching factor and depth are large.

def minMutation(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 roughly O(b^(d/2)) instead of O(b^d) nodes (b = branching factor, 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: use 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 large, bidirectional BFS meeting in the middle is the standard speedup. DFS does not fit, because its first solution is not guaranteed to be the shortest.