Minimum Genetic Mutation

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

Example 1:

Input: startGene = “AACCGGTT”, endGene = “AACCGGTA”, bank = [“AACCGGTA”] Output: 1

Example 2:

Input: startGene = “AACCGGTT”, endGene = “AAACGGTA”, bank = [“AACCGGTA”,“AACCGCTA”,“AAACGGTA”] Output: 2

Constraints:

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

Approach: BFS over the Gene Bank

Algorithm

1. Put the bank genes into a set for O(1) membership checks
2. Run BFS from startGene; each step mutates one of the 8 positions to one of 4 nucleotides
3. A mutated string is enqueued only if it exists in the bank and has not been visited
4. Return the BFS depth when endGene is reached, or -1 if the queue empties

Time & Space Complexity

• Time Complexity: O(N * 8 * 4) - each of the N bank genes generates up to 32 neighbors
• Space Complexity: O(N) - the visited set and the BFS queue

Java Implementation

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

public class MinimumGeneticMutation {

    private static final char[] GENES = {'A', 'C', 'G', 'T'};

    /**
     * Return the minimum number of mutations from startGene to endGene.
     * @param startGene Start string
     * @param endGene Target string
     * @param bank Valid gene strings
     * @return Minimum mutations, or -1
     */
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>();
        for (String gene : bank) {
            bankSet.add(gene);
        }

        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(startGene);
        visited.add(startGene);

        int mutations = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                if (current.equals(endGene)) {
                    return mutations;
                }
                for (String next : neighbors(current)) {
                    if (bankSet.contains(next) && !visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            mutations++;
        }

        return -1;
    }

    private java.util.List<String> neighbors(String gene) {
        java.util.List<String> result = new java.util.ArrayList<>();
        char[] chars = gene.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            for (char c : GENES) {
                if (c == original) {
                    continue;
                }
                chars[i] = c;
                result.add(new String(chars));
            }
            chars[i] = original;
        }
        return result;
    }

    // Test method
    public static void main(String[] args) {
        MinimumGeneticMutation mgm = new MinimumGeneticMutation();
        System.out.println("Input: startGene = \"AACCGGTT\", endGene = \"AACCGGTA\", bank = [\"AACCGGTA\"]");
        System.out.println("Output: " + mgm.minMutation("AACCGGTT", "AACCGGTA", new String[]{"AACCGGTA"})); // Expected: 1

        System.out.println("Input: startGene = \"AACCGGTT\", endGene = \"AAACGGTA\", bank = [\"AACCGGTA\",\"AACCGCTA\",\"AAACGGTA\"]");
        System.out.println("Output: " + mgm.minMutation("AACCGGTT", "AAACGGTA",
                new String[]{"AACCGGTA", "AACCGCTA", "AAACGGTA"})); // Expected: 2
    }
}

Example Walkthrough

For startGene = "AACCGGTT", endGene = "AAACGGTA", bank = [“AACCGGTA”,“AACCGCTA”,“AAACGGTA”]:

1. Level 0: AACCGGTT. Neighbors in bank: AACCGGTA (position 7 -> A)
2. Level 1: AACCGGTA. Neighbors in bank: AACCGCTA (position 4 -> C)
3. Level 2: AACCGCTA -> AAACGGTA (position 2 -> A) reaches the endGene

Result: 2 mutations.

Key Points

1. BFS Depth = Mutation Count: Each BFS level represents one single-character change
2. Small Alphabet: Only 4 nucleotides, so each position has exactly 3 alternatives
3. Bank Constraint: Intermediate strings must be present in the bank
4. Start Not Required: The starting gene may be absent from the bank but is still valid
5. Return -1 on Exhaustion: If no path reaches the endGene, the queue empties and -1 is returned