> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Genetic Mutation Python Solution

> Tested Python solution for LeetCode 433 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 433, [Medium](/catalog/medium). Topics: [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Breadth-First Search](/catalog/topics/breadth-first-search), Bidirectional Search. [View on LeetCode](https://leetcode.com/problems/minimum-genetic-mutation/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 433   # by problem number
lcpy gen -s minimum_genetic_mutation   # by problem name
```

## Problem

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 mutation, return `-1`.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

### Examples

```
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Explanation: One mutation changes the last gene from 'T' to 'A'.
```

```
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'].

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_genetic_mutation/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_genetic_mutation/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(8^2 * n) where n = len(bank), each gene expands 8*4 neighbors
    # Space: O(n)
    def min_mutation(self, start_gene: str, end_gene: str, bank: list[str]) -> int:
        valid = set(bank)
        if start_gene == end_gene:
            return 0
        if end_gene not in valid:
            return -1
        queue: deque[tuple[str, int]] = deque([(start_gene, 0)])
        visited = {start_gene}
        while queue:
            gene, steps = queue.popleft()
            if gene == end_gene:
                return steps
            for i in range(len(gene)):
                for c in "ACGT":
                    if c == gene[i]:
                        continue
                    nxt = gene[:i] + c + gene[i + 1 :]
                    if nxt in valid and nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, steps + 1))
        return -1
```

## Complexity

| Time | Space |
| - | - |
| O(8^2 \* n) where n = len(bank), each gene expands 8\*4 neighbors | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.