Log inSign up
mediumLeetCodeNot Started

Minimum Genetic Mutation

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is 1 mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return *the minimum number of mutations needed to mutate from startGene to endGene*. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Constraints:

  • startGene.length == 8
  • endGene.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • startGene, endGene, and bank[i] consist of only the characters [A, C, G, T].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map discrete string mutation transformations to unweighted graph BFS.
  • Optimize nucleotide substitution checks (8 × 4 = 32 mutations per step).
  • Use HashSet removal for O(1) visited state tracking.
  • Handle validity criteria (endGene must be in bank, startGene need not be).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Identical to Word Ladder, but constrained to 8 characters and 4 alphabet choices (A, C, G, T). Use Breadth-First Search (BFS) for minimal step discovery.

1. DFS with Backtracking

Intuition

Explore all valid one-character mutations recursively using Depth-First Search. Track visited gene strings to prevent infinite cycles. Keep track of the minimum path length to reach endGene.

Algorithm

  1. If endGene is not in bank, return -1.
  2. Initialize visited set.
  3. Define dfs(curr, depth):
  4. If curr == endGene, update minDepth = min(minDepth, depth).
  5. For each gene in bank not in visited differing by exactly 1 character:
  6. visited.add(gene)
  7. dfs(gene, depth + 1)
  8. visited.remove(gene) (backtrack)
  9. Run dfs(startGene, 0).
  10. Return minDepth == infinity ? -1 : minDepth.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6#include <climits>
7
8bool differsByOneChar(const std::string& a, const std::string& b) {
9 int diff = 0;
10 for (int i = 0; i < 8; ++i) {
11 if (a[i] != b[i]) {
12 if (++diff > 1) return false;
13 }
14 }
15 return diff == 1;
16}
17
18void dfsGene(const std::string& curr, const std::string& target, int depth,
19 const std::vector<std::string>& bank, std::vector<bool>& visited, int& minDepth) {
20 if (depth >= minDepth) return;
21 if (curr == target) {
22 minDepth = depth;
23 return;
24 }
25
26 for (size_t i = 0; i < bank.size(); ++i) {
27 if (!visited[i] && differsByOneChar(curr, bank[i])) {
28 visited[i] = true;
29 dfsGene(bank[i], target, depth + 1, bank, visited, minDepth);
30 visited[i] = false;
31 }
32 }
33}
34
35int minMutationDFS(std::string startGene, std::string endGene, std::vector<std::string>& bank) {
36 int minDepth = INT_MAX;
37 std::vector<bool> visited(bank.size(), false);
38 dfsGene(startGene, endGene, 0, bank, visited, minDepth);
39 return minDepth == INT_MAX ? -1 : minDepth;
40}
41
42int main() {
43 std::vector<std::string> bank = {"AACCGGTA"};
44 std::cout << "Min Mutation (DFS): " << minMutationDFS("AACCGGTT", "AACCGGTA", bank) << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(B!) where B is bank.length (B <= 10).
  • Space complexity: O(B) for recursion stack and visited set.

2. Bidirectional BFS

Intuition

Search simultaneously forward from startGene and backward from endGene. In each step, expand the smaller of the two frontier sets. If a mutation generated from one frontier exists in the opposite frontier, the shortest path is found, halving the search depth.

Algorithm

  1. Store bank in a set bankSet. If endGene not in bankSet, return -1.
  2. Initialize beginSet = {startGene}, endSet = {endGene}.
  3. Initialize steps = 0.
  4. While !beginSet.empty() && !endSet.empty():
  5. If beginSet.size() > endSet.size(), swap them.
  6. Create nextSet.
  7. For each gene in beginSet:
  8. Mutate 8 positions with A, C, G, T:
  9. If mutant in endSet, return steps + 1.
  10. If mutant in bankSet:
  11. bankSet.erase(mutant)
  12. nextSet.insert(mutant)
  13. beginSet = nextSet
  14. steps++
  15. Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6
7int minMutationBiBFS(std::string startGene, std::string endGene, std::vector<std::string>& bank) {
8 std::unordered_set<std::string> bankSet(bank.begin(), bank.end());
9 if (!bankSet.count(endGene)) return -1;
10
11 std::unordered_set<std::string> beginSet{startGene};
12 std::unordered_set<std::string> endSet{endGene};
13 bankSet.erase(startGene);
14 bankSet.erase(endGene);
15
16 int steps = 0;
17 const char bases[] = {'A', 'C', 'G', 'T'};
18
19 while (!beginSet.empty() && !endSet.empty()) {
20 if (beginSet.size() > endSet.size()) {
21 std::swap(beginSet, endSet);
22 }
23
24 std::unordered_set<std::string> nextSet;
25 for (std::string gene : beginSet) {
26 for (int i = 0; i < 8; ++i) {
27 char orig = gene[i];
28 for (char b : bases) {
29 gene[i] = b;
30 if (endSet.count(gene)) return steps + 1;
31 if (bankSet.count(gene)) {
32 bankSet.erase(gene);
33 nextSet.insert(gene);
34 }
35 }
36 gene[i] = orig;
37 }
38 }
39 beginSet = nextSet;
40 steps++;
41 }
42 return -1;
43}
44
45int main() {
46 std::vector<std::string> bank = {"AAAACCCC","AAACCCCC","AACCCCCC"};
47 std::cout << "Min Mutation (Bi-BFS): " << minMutationBiBFS("AAAAACCC", "AACCCCCC", bank) << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(B * 32) where B is bank size and 32 is 8 * 4 mutations.
  • Space complexity: O(B) for frontier sets and bank set.

3. Breadth-First Search (BFS)

Intuition

Standard Breadth-First Search is the gold standard for shortest unweighted paths. Store bank in a HashSet. Queue stores (gene, mutations). From each gene, test all 8 × 4 = 32 possible single-nucleotide mutations. If a mutant exists in the bank set, remove it from the set (marking it visited) and enqueue with mutations + 1. The first time endGene is reached, return the mutation count.

Algorithm

  1. Create bankSet from bank. If endGene not in bankSet, return -1.
  2. Initialize queue with (startGene, 0).
  3. While queue is not empty:
  4. pop (gene, mutations)
  5. If gene == endGene, return mutations.
  6. For i = 0 to 7:
  7. For base in ['A', 'C', 'G', 'T']:
  8. Create mutant = gene with character at i replaced by base.
  9. If mutant in bankSet:
  10. bankSet.erase(mutant) (mark visited)
  11. queue.push((mutant, mutations + 1))
  12. Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <queue>
6
7int minMutation(std::string startGene, std::string endGene, std::vector<std::string>& bank) {
8 std::unordered_set<std::string> bankSet(bank.begin(), bank.end());
9 if (!bankSet.count(endGene)) return -1;
10
11 std::queue<std::pair<std::string, int>> q;
12 q.push({startGene, 0});
13
14 const char bases[] = {'A', 'C', 'G', 'T'};
15
16 while (!q.empty()) {
17 auto [gene, mutations] = q.front();
18 q.pop();
19
20 if (gene == endGene) return mutations;
21
22 for (int i = 0; i < 8; ++i) {
23 char orig = gene[i];
24 for (char b : bases) {
25 gene[i] = b;
26 if (bankSet.count(gene)) {
27 bankSet.erase(gene);
28 q.push({gene, mutations + 1});
29 }
30 }
31 gene[i] = orig;
32 }
33 }
34
35 return -1;
36}
37
38int main() {
39 std::vector<std::string> bank = {"AACCGGTA"};
40 std::cout << "Optimal Min Mutation (BFS): " << minMutation("AACCGGTT", "AACCGGTA", bank) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(B * 32 * 8) = O(B) where B is the size of the bank (B <= 10). Generates 32 mutations of length 8 per visited word.
  • Space complexity: O(B) for the bankSet and BFS queue.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with BacktrackingO(B!)O(B)Simple recursive formulation.Explores all possible paths instead of finding the shortest path first.
2.Bidirectional BFSO(B * 32)O(B)Halves search depth; optimal for large branching spaces.Requires synchronizing two frontier sets.
3.Standard BFSOptimalO(B * 32)O(B)Standard, clean, guaranteed minimum mutation count.None for B <= 10.

Common Pitfalls & Crucial Edge Cases

Checking whether startGene is in the bank.

The problem states startGene is assumed to be valid even if not in the bank.

Checking all 26 English letters instead of the 4 nucleotide bases A, C, G, T.

Gene strings only consist of A, C, G, and T.

Crucial Edge Cases to Validate:

  • startGene == endGene — Zero mutations needed; returns 0.
  • endGene not present in bank — Returns -1 immediately.
  • No valid mutation path exists through the bank — Queue empties; returns -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Note the strong similarity to Word Ladder, highlighting the specific constraints (fixed length 8, alphabet size 4).
  2. Explain the BFS choice: uniform cost of 1 mutation per step guarantees minimum steps upon reaching endGene.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Must the startGene be in the bank to be considered valid?

2.What should be returned if endGene is not in the bank?

3.Why does BFS guarantee the minimum number of mutations?

Back to DSA Sheet