Minimum Genetic mutation

433.Minimum Genetic Mutation

Breadth-First Search

String

Hash Table

Problem Statement:

Given a start gene, end gene, and gene bank, return the minimum number of mutations needed to mutate from start to end. Each gene string consists of 'A', 'C', 'G', and 'T'. If there is no valid mutation path, return -1.

Example:

Input:

start = "AACCGGTT"
end = "AACCGGTA"
bank = ["AACCGGTA"]

→

Output:

1

Algorithm:

1. Convert bank to HashSet for O(1) lookup
2. Use BFS to find shortest mutation path
3. Try all possible mutations with A, C, G, T
4. Track visited sequences by removing from bank

Complexity:

Time: O(N * L * 4) | Space: O(N) where N is bank size, L is gene length

Java Solution:

public int minMutation(String start, String end, String[] bank) {
    // Convert bank to HashSet for O(1) lookup
    Set geneBank = new HashSet<>(Arrays.asList(bank));
    
    // Check if end sequence is valid
    if (!geneBank.contains(end)) {
        return -1;
    }
    
    // Valid characters for mutation
    char[] allowedChars = {'A', 'C', 'G', 'T'};
    
    // BFS queue setup
    Queue queue = new LinkedList<>();
    queue.add(start);
    int mutations = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        // Process current level
        for (int i = 0; i < size; i++) {
            String currentGene = queue.poll();
            
            if (currentGene.equals(end)) 
                return mutations;
            
            // Try all possible mutations
            char[] geneArray = currentGene.toCharArray();
            for (int j = 0; j < geneArray.length; j++) {
                char originalChar = geneArray[j];
                
                for (char c : allowedChars) {
                    if (c == originalChar) continue;
                    
                    geneArray[j] = c;
                    String mutatedGene = new String(geneArray);
                    
                    if (geneBank.contains(mutatedGene)) {
                        geneBank.remove(mutatedGene);  // Mark as visited
                        queue.add(mutatedGene);
                    }
                }
                geneArray[j] = originalChar;  // Reset character
            }
        }
        mutations++;
    }
    
    return -1;  // No valid path found
}

Python Solution:

def minMutation(self, start: str, end: str, bank: List[str]) -> int:
    gene_bank = set(bank)
    
    if end not in gene_bank:
        return -1
        
    allowed_chars = ['A', 'C', 'G', 'T']
    queue = deque([start])
    mutations = 0
    
    while queue:
        # Process current level
        for _ in range(len(queue)):
            current = queue.popleft()
            
            if current == end:
                return mutations
                
            # Try all mutations
            for i in range(len(current)):
                for c in allowed_chars:
                    if c != current[i]:
                        mutated = current[:i] + c + current[i+1:]
                        if mutated in gene_bank:
                            gene_bank.remove(mutated)
                            queue.append(mutated)
                            
        mutations += 1
        
    return -1

C++ Solution:

int minMutation(string start, string end, vector& bank) {
    unordered_set gene_bank(bank.begin(), bank.end());
    
    if (!gene_bank.count(end)) 
        return -1;
        
    vector<char> allowed = {'A', 'C', 'G', 'T'};
    queue q{{start}};
    int mutations = 0;
    
    while (!q.empty()) {
        for (int size = q.size(); size > 0; --size) {
            string curr = q.front();
            q.pop();
            
            if (curr == end) 
                return mutations;
                
            // Try all mutations
            for (int i = 0; i < curr.size(); ++i) {
                char orig = curr[i];
                for (char c : allowed) {
                    if (c == orig) continue;
                    curr[i] = c;
                    if (gene_bank.count(curr)) {
                        gene_bank.erase(curr);
                        q.push(curr);
                    }
                }
                curr[i] = orig;
            }
        }
        ++mutations;
    }
    
    return -1;
}