Domain 2MediumCORE

Minimum Genetic Mutation

We are given three inputs: a starting 8-character gene string (start), a target end string (end), and a list of valid intermediate strings called the bank. A mutation is defined as changing exactly one character in the string (e.g., 'A' to 'T'). Crucially, any state we transition into must exist within the provided bank, except for our starting point.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

433. Minimum Genetic Mutation

Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 43.6%


Problem Breakdown

We are given three inputs: a starting 8-character gene string (start), a target end string (end), and a list of valid intermediate strings called the bank. A mutation is defined as changing exactly one character in the string (e.g., ‘A’ to ‘T’). Crucially, any state we transition into must exist within the provided bank, except for our starting point.

Inputs:

  • start: String of length 8 (‘A’, ‘C’, ‘G’, ‘T’)
  • end: Target string (length 8)
  • bank: List of valid strings to transition through or end at.

Outputs:

  • Minimum number of mutations (integers). Return -1 if unreachable.

Constraints & Edge Cases:

  • String length is fixed at 8, so no overflow issues with indices.
  • Alphabet size is small (4 characters), limiting branching factor per position to 3 alternatives.
  • start might not be in the bank; it’s implicitly valid as our origin.
  • If end is not present in the bank at all, we cannot reach a “valid” state there, so return -1 (though BFS naturally handles this by ignoring non-bank nodes).

Intuition

This problem asks for the shortest path between two states (start and end) where intermediate steps are constrained. This is a classic Shortest Path in an Unweighted Graph scenario. The gene strings represent nodes, and valid mutations (differing by one character) represent edges connecting them.

A brute-force Depth First Search (DFS) would explore all possible paths to find the minimum depth, but without pruning visited states or tracking distance properly, it could get stuck in cycles or traverse deep suboptimal branches first. Since we want the minimum number of mutations and edge weights are uniform (1 mutation = 1 step), Breadth-First Search (BFS) is the optimal choice. BFS guarantees finding the shortest path level-by-level.

To optimize lookups, I should convert the bank list into a hash set (O(1) lookup) rather than iterating through it linearly every time we check for validity. This prevents an O(N^2) complexity where N is bank size.

Approach

  1. Preprocessing: Convert the bank list to a Set for fast membership testing. If end isn’t in this set, return -1 immediately (optimization).
  2. BFS Initialization: Use a queue (deque) storing tuples of (current_gene_string). We also need to track distance/depth. A common pattern is either pushing (node, depth) or using two queues for levels; here I’ll use collections.deque and store the string in the queue while maintaining an external counter or dictionary mapping node -> steps taken (though a simple tuple approach works fine).
  3. Visited Tracking: Maintain a set of visited genes to avoid processing the same gene multiple times, which prevents cycles and redundant work. Add start to this immediately if it’s not in bank? Actually, standard BFS logic: add start to queue/visited. If we encounter a neighbor that is valid (in bank) AND unvisited, push to queue.
  4. Neighbor Generation: For each gene popped from the queue, iterate through all indices 0 to 7. Try changing character at index i with ‘A’, ‘C’, ‘G’, or ‘T’. If the new string is in our bank set and not visited:
    • Mark as visited.
    • Push to queue.
    • Increment step count (or check if this neighbor equals end).
  5. Termination: Return steps when we pop a node that matches end, or return -1 if the queue empties without finding it.

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L), where NN is the number of valid genes in the bank and LL is the string length (8). For each gene we visit, we generate up to 24 neighbors (3×83 \times 8 positions ×\times alphabet size check), but most won’t be in the set. Since BFS visits each reachable node once, it’s linear with respect to the bank size for practical purposes given fixed LL.
  • Space Complexity: O(N)O(N) to store the bank set and visited nodes/queue elements.

Solution

from collections import deque
from typing import List

def minMutation(start: str, end: str, bank: List[str]) -> int:
    # Convert list to set for O(1) lookups
    valid_genes = set(bank)
    
    # Optimization: If target is not in the bank of valid genes, we can't reach it.
    if end not in valid_genes:
        return -1
    
    # BFS Queue stores just the current gene string; 
    # We track distance separately or store (gene, steps).
    queue = deque([start])
    
    # Keep track of visited nodes to prevent cycles and redundant processing
    visited = {start}
    
    mutations_count = 0
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            current_gene = queue.popleft()
            
            if current_gene == end:
                return mutations_count
            
            # Try changing each character position (A, C, G, T)
            chars = ['A', 'C', 'G', 'T']
            for i in range(8):
                original_char = current_gene[i]
                
                for char_to_try in chars:
                    if char_to_try == original_char:
                        continue
                    
                    # Construct the mutated string
                    new_gene = current_gene[:i] + char_to_try + current_gene[i+1:]
                    
                    # Check validity and visitation status
                    if new_gene not in visited and new_gene in valid_genes:
                        queue.append(new_gene)
                        visited.add(new_gene)
        
        mutations_count += 1
        
    return -1

# Example usage (commented out for submission):
# print(minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA","AACCGCTA","AAACGGTA"])) # Expected: 2

Edge Cases Handled

  • Target not in bank: The check if end not in valid_genes handles this immediately, returning -1.
  • Start equals End: Although the problem statement assumes they are different, if they were identical, the loop would return 0 on first pop (before incrementing count), which is correct logic for BFS distance from self. However, per constraints, we skip explicit check to save cycles.
  • Unreachable Target: If queue empties and end hasn’t been reached, returns -1 at end of function.
  • Duplicate Genes in Bank: Using a set automatically deduplicates the bank list before processing.