AlgoMaster Logo

Minimum Genetic Mutation

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're given two gene strings of length 8, each composed of the characters A, C, G, and T. We need to find the minimum number of single-character mutations to transform startGene into endGene, with the constraint that every intermediate gene (and the final one) must exist in the bank.

This is a shortest path problem. Each valid gene is a node. Two nodes are connected if they differ by exactly one character. We want the shortest path from startGene to endGene through the graph of valid genes.

Every mutation changes exactly one character, so every edge has the same cost of 1. The minimum number of mutations is the number of edges on the shortest path in an unweighted graph, which is what breadth-first search computes.

Key Constraints:

  • bank.length <= 10 → At most 10 valid genes, so the graph is small. The choice between approaches comes down to clarity rather than asymptotic performance.
  • Gene strings are exactly 8 characters → Comparing two genes takes O(8) = O(1) time. Generating every one-character mutation of a gene is bounded at 8 positions times 3 alternative characters = 24 candidates.
  • Characters are only A, C, G, T → A fixed 4-character alphabet bounds the branching factor when generating mutations.

Approach 1: BFS with Bank Comparison

Intuition

Model the genes as a graph where each gene is a node and edges connect genes that differ by exactly one character. BFS explores the graph level by level, so the first time it reaches endGene, the level number equals the fewest mutations needed.

Starting from startGene, each BFS step looks for the current gene's neighbors. A neighbor is any gene in the bank that differs from the current gene by exactly one character and has not been visited. To test for a single-character difference, walk through all 8 positions and count mismatches; the two genes are neighbors when the count is exactly 1.

A mutation counter increases by one per BFS level. The first time endGene appears, that counter is the answer. If the queue empties first, no valid path exists and the answer is -1.

Algorithm

  1. If startGene equals endGene, return 0 (no mutations needed).
  2. If endGene is not in the bank, return -1 immediately (it can never be reached).
  3. Create a queue and add startGene to it. Create a visited set and add startGene.
  4. Initialize mutations = 0.
  5. While the queue is not empty:
    • Process all genes at the current BFS level (use the queue's current size).
    • For each gene in the current level, check every gene in the bank.
    • If a bank gene differs by exactly one character and hasn't been visited, add it to the queue and mark it as visited.
    • If that bank gene equals endGene, return mutations + 1.
  6. Increment mutations after processing each level.
  7. If the queue empties without finding endGene, return -1.

Example Walkthrough

1Start: current = "AACCGGTT", mutations = 0
0
A
1
A
2
C
3
C
4
G
5
G
6
T
7
T
1/7

Code

Finding neighbors by scanning the whole bank costs work proportional to the bank size on every step. The next approach finds neighbors by generating the fixed set of one-character mutations instead, so neighbor generation no longer depends on how large the bank is.

Approach 2: BFS with Mutation Generation (Optimal)

Intuition

Rather than comparing the current gene against every bank entry, generate all one-character mutations of the current gene and test each one for membership in the bank.

A gene has 8 positions. At each position, the current character can be replaced by any of the other 3 characters from {A, C, G, T}, which gives 8 * 3 = 24 candidate mutations per gene. With all bank genes stored in a hash set, each membership test is O(1).

Neighbor generation now depends only on the gene length (8) and the alphabet size (4), both fixed constants, instead of the bank size. The same neighbor-by-substitution pattern applies to any single-character transformation problem over a fixed alphabet.

Algorithm

  1. If startGene equals endGene, return 0.
  2. Put all bank genes into a hash set for O(1) lookup.
  3. If endGene is not in the set, return -1.
  4. Create a queue with startGene and a visited set.
  5. While the queue is not empty:
    • Process all genes at the current BFS level.
    • For each gene, try all 8 positions and all 4 characters.
    • If the mutated gene is in the bank set and not yet visited, add it to the queue.
    • If it equals endGene, return the current mutation count + 1.
  6. Increment mutation count after each level.
  7. Return -1 if the queue empties.

Example Walkthrough

1Start: current = "AAAAACCC", mutations = 0
0
A
1
A
2
A
3
A
4
A
5
C
6
C
7
C
1/7

Code

BFS finds the shortest path directly. DFS with backtracking solves the same problem differently: it explores complete mutation paths one at a time and keeps the smallest length that reaches endGene.

Approach 3: DFS with Backtracking

Intuition

DFS explores one full path before trying the next: pick a neighbor, recurse, undo the choice (backtrack), then try the next neighbor. Unlike BFS, DFS can reach endGene through a long path before a shorter one, so it cannot stop at the first arrival. It must explore every path and keep the minimum length found.

Tracking the minimum is correct because every path from startGene to endGene is considered, and the answer is the shortest among them. A pruning check skips any path whose length has already reached the best result so far, since extending it cannot improve the answer. Backtracking removes each gene from the visited set after its recursion returns, which lets the same gene be reused on a different branch and keeps the search from missing a shorter route that passes through it. With bank size at most 10, the number of paths stays small.

Algorithm

  1. Put all bank genes into a set for O(1) lookup.
  2. If startGene equals endGene, return 0.
  3. If endGene is not in the set, return -1.
  4. Create a visited set to avoid cycles.
  5. Define a recursive function dfs(current, mutations):
    • If current equals endGene, update the minimum.
    • Prune if current path is already longer than the best found.
    • Try all 8 positions and all 4 characters.
    • If the mutated gene is in the bank and not visited, mark it as visited, recurse, then unmark (backtrack).
  6. Return the minimum, or -1 if no path exists.

Example Walkthrough

1DFS start: current = "AACCGGTT", mutations = 0, minResult = inf. bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
0
A
1
A
2
C
3
C
4
G
5
G
6
T
7
T
1/8

Code