Minimum Genetic Mutation

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 startGene to an endGene where one mutation is defined as one single character changed in the gene string.

• There is a bank of valid gene mutations. Only mutations in the bank are allowed.
• Return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such mutation sequence, return -1.

Key Insight

• This is a shortest path problem on a graph where each gene is a node.
• Two genes are connected if they differ by exactly one character and the target gene is in the bank.
• BFS finds the shortest path; DFS explores all possibilities.

Examples

startGene	endGene	bank	Output	Explanation
"AACCCCCC"	"AACCCCTA"	["AACCCCTA"]	1	Direct mutation from start to end in one step.
"AACCCCCC"	"AAACCCTA"	["AACCCCTA","AACCCCCA","AAACCCTA","AAACCCCA","AAACCCTA"]	2	Path: AACCCCCC → AACCCCTA → AAACCCTA
"AAAAAAAA"	"CCCCCCCC"	["AAAAAAAC","AAAAAACA","AAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCC"]	4	Multiple valid mutation paths exist.
"AACCCCCC"	"AACCCCCB"	["AACCCCTA"]	-1	End gene not in bank or unreachable.

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', and 'T'.
• startGene != endGene

Real-World Applications

Where this pattern appears

• Bioinformatics and genomics — Finding minimum evolutionary distance between DNA or protein sequences in phylogenetic analysis.
• Chemical structure transformation — Computing shortest transformation paths between chemical compounds where each bond/atom change is one mutation.
• Network routing — Finding minimum hop count paths in communication networks where each valid transition is a known route.
• State space exploration — Any problem requiring shortest path through valid state transitions with restricted moves (word ladder, chemical synthesis).

Complexity Comparison

Approach	Time	Space	Notes
BFS	O(n)	O(n)	First approach
DFS	O(n)	O(n)	Second approach

Approach 1: BFS

★ Recommended

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

minimum_genetic_mutation_bfs.py

from collections import deque

def minMutation(startGene, endGene, bank):
    """BFS to find minimum mutations."""
    if endGene not in bank:
        return -1

    bank_set = set(bank)
    queue = deque([(startGene, 0)])
    visited = {startGene}
    chars = ['A', 'C', 'G', 'T']

    while queue:
        gene, mutations = queue.popleft()
        if gene == endGene:
            return mutations

        for i in range(len(gene)):
            for char in chars:
                if char != gene[i]:
                    new_gene = gene[:i] + char + gene[i+1:]
                    if new_gene in bank_set and new_gene not in visited:
                        visited.add(new_gene)
                        queue.append((new_gene, mutations + 1))

    return -1

C++

minimum_genetic_mutation_bfs.cpp

class Solution {
    // TODO: Implement
};

Java

MinimumGeneticMutationBfs.java

import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) return -1;

        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        Set<String> visited = new HashSet<>();
        visited.add(startGene);
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (curr.equals(endGene)) return steps;

                for (String next : getNeighbors(curr, bankSet)) {
                    if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            steps++;
        }
        return -1;
    }

    private List<String> getNeighbors(String gene, Set<String> bank) {
        List<String> neighbors = new ArrayList<>();
        char[] genes = gene.toCharArray();
        char[] chars = {'A', 'C', 'G', 'T'};

        for (int i = 0; i < genes.length; i++) {
            char old = genes[i];
            for (char c : chars) {
                if (c != old) {
                    genes[i] = c;
                    String neighbor = new String(genes);
                    if (bank.contains(neighbor)) neighbors.add(neighbor);
                }
            }
            genes[i] = old;
        }
        return neighbors;
    }
}

JavaScript

minimum_genetic_mutation_bfs.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

minimum_genetic_mutation_bfs.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

minimum_genetic_mutation_bfs.go

package main

// TODO: Implement solution

Approach 2: DFS

✓ Simple

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

minimum_genetic_mutation_dfs.py

def minMutation(startGene, endGene, bank):
    """DFS with memoization to find minimum mutations."""
    if endGene not in bank:
        return -1

    bank_set = set(bank)
    memo = {}
    chars = ['A', 'C', 'G', 'T']

    def dfs(gene):
        if gene == endGene:
            return 0
        if gene in memo:
            return memo[gene]

        result = float('inf')
        for i in range(len(gene)):
            for char in chars:
                if char != gene[i]:
                    new_gene = gene[:i] + char + gene[i+1:]
                    if new_gene in bank_set:
                        result = min(result, 1 + dfs(new_gene))

        memo[gene] = result
        return result

    ans = dfs(startGene)
    return ans if ans != float('inf') else -1

C++

minimum_genetic_mutation_dfs.cpp

class Solution {
    // TODO: Implement
};

Java

MinimumGeneticMutationDfs.java

import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) return -1;

        Set<String> visited = new HashSet<>();
        return dfs(startGene, endGene, bankSet, visited);
    }

    private int dfs(String curr, String end, Set<String> bank, Set<String> visited) {
        if (curr.equals(end)) return 0;
        visited.add(curr);
        int minSteps = Integer.MAX_VALUE;

        for (String next : getNeighbors(curr, bank, visited)) {
            int steps = dfs(next, end, bank, visited);
            if (steps != -1) minSteps = Math.min(minSteps, steps + 1);
        }

        return minSteps == Integer.MAX_VALUE ? -1 : minSteps;
    }

    private List<String> getNeighbors(String gene, Set<String> bank, Set<String> visited) {
        List<String> neighbors = new ArrayList<>();
        char[] genes = gene.toCharArray();
        char[] chars = {'A', 'C', 'G', 'T'};

        for (int i = 0; i < genes.length; i++) {
            char old = genes[i];
            for (char c : chars) {
                if (c != old) {
                    genes[i] = c;
                    String neighbor = new String(genes);
                    if (bank.contains(neighbor) && !visited.contains(neighbor)) {
                        neighbors.add(neighbor);
                    }
                }
            }
            genes[i] = old;
        }
        return neighbors;
    }
}

JavaScript

minimum_genetic_mutation_dfs.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

minimum_genetic_mutation_dfs.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

minimum_genetic_mutation_dfs.go

package main

// TODO: Implement solution

Interview Tips

Key trade-offs to discuss

• Approach 1 vs Approach 2 trade-offs
• Edge cases and how to handle them
• Follow-up questions

← Previous
#909 Snakes and Ladders Next
#127 Word Ladder →