# Minimum Genetic Mutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-genetic-mutation)
Canonical: https://scaleengineer.com/dsa/problems/minimum-genetic-mutation
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, String
**Companies:** [X](https://scaleengineer.com/companies/x)
---
## 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 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']`.

# Approaches
## BFS by Scanning Bank for Neighbors
This approach models the problem as finding the shortest path in a graph. The nodes of the graph are the valid gene strings (`startGene` and the genes in the `bank`), and an edge exists between two genes if they differ by a single character. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph like this.

We start a BFS from `startGene`. In each step, we explore all unvisited neighbors of the current gene. A neighbor is defined as a gene within the `bank` that is exactly one mutation away. We continue this search level by level. The level number corresponds to the number of mutations. The search terminates when we find the `endGene`, and we return the current level count.
**Time:** O(N^2 * L), where N is the number of genes in the `bank` and L is the length of a gene. In the worst case, for each of the N+1 genes we visit, we iterate through the entire `bank` of N genes to find neighbors, and each comparison takes O(L) time. · **Space:** O(N * L), where N is the number of genes in the `bank` and L is the length of a gene string. This space is used for the queue and the `visited` set.
**Pros:** The logic is straightforward and directly translates the problem into a graph traversal.; It's guaranteed to find the shortest path if one exists.
**Cons:** This approach is inefficient because for every gene we process, we scan the entire `bank` to find its neighbors. This results in a quadratic time complexity relative to the size of the bank, which is slow for larger banks.
### Explanation
The algorithm works by performing a level-order traversal (BFS) starting from the `startGene`. We use a queue to manage the genes to visit and a set to keep track of visited genes to prevent redundant processing and infinite loops. At each level of the BFS, we represent one mutation step. We iterate through all genes in the `bank` to find valid next steps (neighbors) for the current gene. A gene from the bank is a valid neighbor if it's one character different from the current gene and hasn't been visited before. If we find such a neighbor, we add it to the queue for the next level. If we successfully reach the `endGene`, the current level count is the minimum number of mutations. If the queue becomes empty before we find the `endGene`, no path exists.

```java
import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>(Arrays.asList(bank));
        // We can only mutate to genes in the bank, so if a gene is not in the bank, we can't visit it.
        // We use the visited set to remove genes from consideration once they are added to the queue.

        queue.add(startGene);
        // Note: startGene might not be in the bank, but it's our starting point.
        // We don't need to add it to visited because we won't encounter it again in the bank.

        int mutations = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String currentGene = queue.poll();
                if (currentGene.equals(endGene)) {
                    return mutations;
                }

                // Find neighbors by iterating through the bank
                // This is inefficient but a valid approach.
                // We need a way to iterate over the remaining valid genes.
                // A copy of the bank or iterating and checking against a visited set works.
                for (String bankGene : bank) {
                    if (visited.contains(bankGene) && isMutation(currentGene, bankGene)) {
                        // Add to queue and mark as visited (by removing from the set of available genes)
                        queue.add(bankGene);
                        visited.remove(bankGene);
                    }
                }
            }
            mutations++;
        }

        return -1;
    }

    private boolean isMutation(String gene1, String gene2) {
        int diff = 0;
        for (int i = 0; i < gene1.length(); i++) {
            if (gene1.charAt(i) != gene2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}
```
### Algorithm
*   Initialize a queue and add the `startGene`.
*   Use a `Set` called `visited` to keep track of genes from the `bank` that have been processed to avoid cycles.
*   Initialize a variable `mutations` to 0.
*   Start a Breadth-First Search. In each level of the search, process all genes currently in the queue.
*   For each `currentGene` dequeued:
    *   If `currentGene` equals `endGene`, the shortest path is found. Return `mutations`.
    *   Iterate through every gene in the `bank`.
    *   For each `bankGene`, check if it's a valid one-step mutation from `currentGene` and if it has not been visited.
    *   A valid mutation is a gene that differs by exactly one character.
    *   If it's a valid and unvisited mutation, add it to the queue and the `visited` set.
*   After processing all genes at the current level, increment `mutations`.
*   If the queue becomes empty and `endGene` has not been reached, it means no such mutation path exists. Return -1.

## Optimized BFS with On-the-fly Mutation Generation
This approach improves upon the basic BFS by changing how we find neighbors. Instead of scanning the entire `bank` repeatedly, we take the `currentGene` and proactively generate all its possible one-character mutations. Then, for each generated mutation, we check if it's a valid gene by looking it up in a pre-populated `Set` of bank genes.

This avoids the expensive O(N) scan for neighbors inside the main BFS loop. Since the gene length (8) and alphabet size (4) are small and constant, generating potential neighbors is a fast operation. This optimization significantly reduces the time complexity, making it linear with respect to the size of the bank.
**Time:** O(N * L + N * L^2 * A). The first term is for building the `bankSet`. The second term is for the BFS, where we may visit up to N nodes, and for each node, we generate L*A neighbors, with string operations taking O(L). Since L and A are constants (8 and 4), the complexity simplifies to O(N * L^2). This is significantly better than O(N^2 * L) for the given constraints (N <= 10, L = 8). · **Space:** O(N * L), where N is the number of genes in the `bank` and L is the length of a gene. This space is required for the `bankSet`, `visited` set, and the queue.
**Pros:** Much more efficient than the naive BFS, with a time complexity that is linear in the size of the bank.; The number of neighbor-generation operations is constant for each gene, independent of the bank size.
**Cons:** While more efficient than the previous approach, it still explores the search space from a single direction, which can be suboptimal if the path from start to end is long.
### Explanation
The core idea is to optimize neighbor discovery. We begin by converting the `bank` array into a `HashSet` for constant-time lookups. This setup costs O(N * L). The BFS proceeds as usual, but finding the next valid states is different. For a given gene, we iterate through each of its 8 characters. For each character, we try substituting it with the other 3 possible characters ('A', 'C', 'G', 'T'). This gives us 8 * 3 = 24 potential mutations. For each potential mutation, we check if it's in our `bankSet` and if we've visited it before. If it's a valid and new gene, we add it to our queue. This method is much faster than comparing the current gene with every other gene in the bank.

```java
import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) {
            return -1;
        }

        char[] charSet = new char[]{'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.add(startGene);
        visited.add(startGene);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentGene = queue.poll();
                if (currentGene.equals(endGene)) {
                    return level;
                }

                char[] currentGeneChars = currentGene.toCharArray();
                for (int j = 0; j < currentGeneChars.length; j++) {
                    char oldChar = currentGeneChars[j];
                    for (char c : charSet) {
                        if (c == oldChar) continue;
                        currentGeneChars[j] = c;
                        String nextGene = new String(currentGeneChars);
                        if (!visited.contains(nextGene) && bankSet.contains(nextGene)) {
                            visited.add(nextGene);
                            queue.add(nextGene);
                        }
                    }
                    currentGeneChars[j] = oldChar; // Backtrack to the original character
                }
            }
            level++;
        }
        return -1;
    }
}
```
### Algorithm
*   First, add all genes from the `bank` into a `Set` for efficient O(1) average time lookups. Let's call it `bankSet`.
*   If `endGene` is not in `bankSet`, a mutation is impossible, so return -1.
*   Initialize a queue for BFS with `startGene`.
*   Initialize a `Set` called `visited` to track genes that have been added to the queue. Add `startGene` to it.
*   Start the BFS, processing level by level, with each level representing one mutation.
*   For each `currentGene` dequeued:
    *   If `currentGene` equals `endGene`, return the current level count.
    *   Generate all possible one-character mutations of `currentGene`.
    *   For each character position `i` from 0 to 7:
        *   For each possible character `c` in `{'A', 'C', 'G', 'T'}`:
            *   Create a `nextGene` by changing the character at position `i` to `c`.
            *   If `nextGene` exists in `bankSet` and has not been visited, add it to the queue and the `visited` set.
*   If the queue becomes empty before reaching `endGene`, return -1.

## Bidirectional Breadth-First Search
Bidirectional BFS is a powerful optimization for shortest path problems. It works by running two simultaneous BFS searches: one starting from `startGene` (the forward search) and another from `endGene` (the backward search). The algorithm terminates as soon as a node from one search frontier is discovered by the other, indicating that a path has been found.

By searching from both ends, the total search space explored is drastically reduced. If the shortest path has a length of `d` and the branching factor is `b`, a standard BFS explores roughly `b^d` nodes, whereas a bidirectional BFS explores roughly `2 * b^(d/2)` nodes. This makes it the most efficient approach, especially as the distance between the start and end nodes increases.
**Time:** O(N * L^2). While the worst-case asymptotic complexity is the same as the optimized single-direction BFS, its practical performance is much better. It explores O(b^(d/2)) nodes instead of O(b^d), where `d` is the path length and `b` is the branching factor. This makes it significantly faster if a path exists. · **Space:** O(N * L), where N is the number of genes in the `bank` and L is the length of a gene. This space is used to store the two search frontiers (`beginSet`, `endSet`) and the `visited` set.
**Pros:** The most efficient approach in practice due to the significant reduction in the search space.; Guaranteed to find the shortest path.
**Cons:** The implementation is slightly more complex than a standard BFS, requiring management of two sets of nodes and ensuring the smaller one is always expanded.
### Explanation
This approach aims to find the meeting point between two expanding frontiers. We maintain two sets, `beginSet` and `endSet`, which represent the frontiers of the search from the start and end genes, respectively. In each step, we expand the smaller of the two frontiers to minimize the work done per level. For each gene in the smaller set, we generate all its valid, unvisited one-step mutations. Before adding a new mutation to the next level's frontier, we check if it already exists in the other frontier. If it does, we have found a connection, and the shortest path is the sum of the levels from both directions. If not, we add it to the list for the next level of the current search direction. This continues until the frontiers meet or one of them can no longer be expanded.

```java
import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) {
            return -1;
        }

        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        beginSet.add(startGene);
        endSet.add(endGene);

        Set<String> visited = new HashSet<>();
        visited.add(startGene);
        // We don't add endGene to visited initially because the beginSet search needs to be able to find it.
        // It will be added when the endSet is expanded.

        int level = 0;
        char[] charSet = {'A', 'C', 'G', 'T'};

        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            // Optimization: always expand the smaller set
            if (beginSet.size() > endSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }

            Set<String> nextLevelSet = new HashSet<>();
            for (String gene : beginSet) {
                char[] geneChars = gene.toCharArray();
                for (int i = 0; i < geneChars.length; i++) {
                    char oldChar = geneChars[i];
                    for (char c : charSet) {
                        geneChars[i] = c;
                        String nextGene = new String(geneChars);

                        if (endSet.contains(nextGene)) {
                            return level + 1;
                        }

                        if (!visited.contains(nextGene) && bankSet.contains(nextGene)) {
                            visited.add(nextGene);
                            nextLevelSet.add(nextGene);
                        }
                    }
                    geneChars[i] = oldChar; // Backtrack
                }
            }
            beginSet = nextLevelSet;
            level++;
        }
        return -1;
    }
}
```
### Algorithm
*   First, add all genes from the `bank` into a `Set` for efficient lookups. If `endGene` is not in the set, return -1.
*   Initialize two sets of nodes to visit: `beginSet` containing just `startGene`, and `endSet` containing just `endGene`.
*   Initialize a `visited` set to keep track of all nodes encountered by either search to prevent cycles. Add `startGene` to `visited`.
*   Initialize a `level` counter to 0.
*   While both `beginSet` and `endSet` are not empty:
    *   To keep the search balanced, always choose the smaller of the two sets to expand in the current level.
    *   Create a `nextLevelSet` to store the neighbors of the genes in the chosen set.
    *   For each `gene` in the smaller set:
        *   Generate all its one-character mutations.
        *   For each `nextGene`:
            *   If `nextGene` is present in the *other* set (`endSet` or `beginSet`), the two search frontiers have met. Return `level + 1`.
            *   If `nextGene` is in the `bankSet` and has not been `visited`, add it to `nextLevelSet` and `visited`.
    *   Replace the smaller set with `nextLevelSet` for the next iteration.
    *   Increment the `level`.
*   If the loop finishes (one of the sets becomes empty), no path exists. Return -1.

# Solutions
### Java

```java
class Solution {
public
  int minMutation(String start, String end, String[] bank) {
    Set<String> s = new HashSet<>();
    for (String b : bank) {
      s.add(b);
    }
    Map<Character, String> mp = new HashMap<>(4);
    mp.put('A', "TCG");
    mp.put('T', "ACG");
    mp.put('C', "ATG");
    mp.put('G', "ATC");
    Deque<Pair<String, Integer>> q = new LinkedList<>();
    q.offer(new Pair<>(start, 0));
    while (!q.isEmpty()) {
      Pair<String, Integer> p = q.poll();
      String t = p.getKey();
      int step = p.getValue();
      if (end.equals(t)) {
        return step;
      }
      for (int i = 0; i < t.length(); ++i) {
        for (char c : mp.get(t.charAt(i)).toCharArray()) {
          String next = t.substring(0, i) + c + t.substring(i + 1);
          if (s.contains(next)) {
            q.offer(new Pair<>(next, step + 1));
            s.remove(next);
          }
        }
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMutation(string start, string end, vector<string> &bank) {
    unordered_set<string> s;
    for (auto &b : bank)
      s.insert(b);
    unordered_map<char, string> mp;
    mp['A'] = "TCG";
    mp['T'] = "ACG";
    mp['C'] = "ATG";
    mp['G'] = "ATC";
    queue<pair<string, int>> q;
    q.push({start, 0});
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      string t = p.first;
      int step = p.second;
      if (t == end)
        return step;
      for (int i = 0; i < t.size(); ++i) {
        for (char c : mp[t[i]]) {
          string next = t.substr(0, i) + c + t.substr(i + 1, t.size() - i - 1);
          if (s.count(next)) {
            q.push({next, step + 1});
            s.erase(next);
          }
        }
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int: s = set(bank) q = deque([(start, 0)]) mp = {'A': 'TCG', 'T': 'ACG', 'C': 'ATG', 'G': 'ATC'} while q: t, step = q . popleft() if t == end: return step for i, v in enumerate(t): for j in mp[v]: next = t[: i] + j + t[i + 1:] if next in s: q . append((next, step + 1)) s . remove(next) return - 1

```