Minimum Genetic Mutation

Medium
469.

Minimum Genetic Mutation

Minimum Genetic Mutation is a medium coding problem on strings, hash table and breadth-first search, asked in Amazon, Google, Microsoft and Twitter interviews.

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 == 8
  • 0 <= bank.length <= 10
  • All genes use only the characters A, C, G and T.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} startGene
 * @param {string} endGene
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function(startGene, endGene, bank) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 == 8
  • 0 <= bank.length <= 10
  • All genes use only the characters A, C, G and T.

Hints for Minimum Genetic Mutation

  1. 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.

  2. Hint 2

    Breadth-first search from startGene, expanding only to bank genes one character away.

  3. 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

  1. Frontier = [startGene], level = 0.
  2. For each gene, for each unused bank gene differing in exactly one position: return level + 1 if it is the target, else mark used and add to the next frontier.
  3. 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 -1

Java

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