Minimum Genetic Mutation — Solution in Python, Java & C++
Minimum Genetic Mutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Genetic Mutation is a medium coding problem on strings, hash table and breadth-first search, asked in Amazon, Google, Microsoft and Twitter interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Breadth-First Search
- Asked at: Amazon, Google, Microsoft, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A gene string is eight characters long, each one of 'A', 'C', 'G' or 'T'. A mutation changes exactly one character, and every intermediate gene must appear in bank.
Given startGene, endGene and bank, return the minimum number of mutations that turns the first into the second, or -1 if it is impossible.
Example 1
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Example 2
Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Example 3
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = []
Output: -1
Constraints
startGene.length == endGene.length == 80 <= bank.length <= 10All genes use only the characters A, C, G and T.
Hints for Minimum Genetic Mutation
Hint 1
Each gene is a node and a single-character change is an edge, so this is a shortest path on an unweighted graph.
Hint 2
Breadth-first search from
startGene, expanding only to bank genes one character away.Hint 3
Mark bank genes as used the moment you enqueue them so no gene is revisited.
How to solve Minimum Genetic Mutation
Genes are nodes and single-character changes are edges; BFS level by level from startGene, expanding only to unused bank genes exactly one character away.
Approach
- Frontier =
[startGene],level = 0. - For each gene, for each unused bank gene differing in exactly one position: return
level + 1if it is the target, else mark used and add to the next frontier. - Return -1 when the frontier empties.
Why it works
All mutations cost one, so BFS finds the shortest path; marking on enqueue keeps each gene expanded once.
Complexity
- Time —
O(levels · |bank| · 8) - Space —
O(|bank|)
Pitfalls
- The target must itself be in the bank; scanning the bank enforces that.
Reference solution
Python
def minMutation(startGene: str, endGene: str, bank) -> int:
used = [False] * len(bank)
frontier = [startGene]
level = 0
while frontier:
nxt = []
for gene in frontier:
for i, candidate in enumerate(bank):
if used[i]:
continue
diff = sum(1 for a, b in zip(candidate, gene) if a != b)
if diff != 1:
continue
if candidate == endGene:
return level + 1
used[i] = True
nxt.append(candidate)
frontier = nxt
level += 1
return 0 if startGene == endGene else -1Java
public static int minMutation(String startGene, String endGene, String[] bank) {
boolean[] used = new boolean[bank.length];
List<String> frontier = new ArrayList<>();
frontier.add(startGene);
int level = 0;
while (!frontier.isEmpty()) {
List<String> next = new ArrayList<>();
for (String gene : frontier) {
for (int i = 0; i < bank.length; i++) {
if (used[i]) continue;
int diff = 0;
for (int k = 0; k < bank[i].length(); k++) {
if (bank[i].charAt(k) != gene.charAt(k)) diff++;
}
if (diff != 1) continue;
if (bank[i].equals(endGene)) return level + 1;
used[i] = true;
next.add(bank[i]);
}
}
frontier = next;
level++;
}
return startGene.equals(endGene) ? 0 : -1;
}C++
int minMutation(string startGene, string endGene, vector<string>& bank) {
vector<bool> used(bank.size(), false);
vector<string> frontier;
frontier.push_back(startGene);
int level = 0;
while (!frontier.empty()) {
vector<string> next;
for (const string& gene : frontier) {
for (size_t i = 0; i < bank.size(); i++) {
if (used[i]) continue;
int diff = 0;
for (size_t k = 0; k < bank[i].size(); k++) {
if (bank[i][k] != gene[k]) diff++;
}
if (diff != 1) continue;
if (bank[i] == endGene) return level + 1;
used[i] = true;
next.push_back(bank[i]);
}
}
frontier = next;
level++;
}
return startGene == endGene ? 0 : -1;
}JavaScript
var minMutation = function(startGene, endGene, bank) {
const used = bank.map(function() { return false; });
let frontier = [startGene];
let level = 0;
while (frontier.length > 0) {
const next = [];
for (let f = 0; f < frontier.length; f++) {
for (let i = 0; i < bank.length; i++) {
if (used[i]) continue;
let diff = 0;
for (let k = 0; k < bank[i].length; k++) {
if (bank[i].charAt(k) !== frontier[f].charAt(k)) diff++;
}
if (diff !== 1) continue;
if (bank[i] === endGene) return level + 1;
used[i] = true;
next.push(bank[i]);
}
}
frontier = next;
level++;
}
return startGene === endGene ? 0 : -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets