Skip to content

433. Minimum Genetic Mutation

On LeetCode ->

Problem

Find the fewest single-character mutations needed to change startGene into endGene. Every gene after the start must appear in bank; return -1 if no valid sequence exists.

start="AACCGGTT", end="AAACGGTA"
bank={"AACCGGTA", "AACCGCTA", "AAACGGTA"}
path: AACCGGTT -> AACCGGTA -> AAACGGTA
output: 2

Key trick

Treat each valid gene as a graph node and use BFS, since every mutation has equal cost.

Trap

  • Checking whether endGene is in bank before handling startGene == endGene.
  • Allowing mutations absent from bank.
  • Failing to remove visited genes, causing repeated work.
  • Returning the number of visited genes instead of the number of mutation edges.

Why is it interesting?

It disguises an unweighted shortest-path problem as string transformation.

Python solution

from collections import deque


class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str],) -> int:
        if startGene == endGene:
            return 0

        genes = set(bank)
        if endGene not in genes:
            return -1

        q = deque([(startGene, 0)])
        genes.discard(startGene)

        while q:
            gene, mutations = q.popleft()

            for i, ch in enumerate(gene):
                for letter in "ACGT":
                    if letter == ch:
                        continue

                    nxt = gene[:i] + letter + gene[i + 1:]

                    if nxt == endGene:
                        return mutations + 1

                    if nxt in genes:
                        # Removing on discovery prevents duplicate enqueues.
                        genes.remove(nxt)
                        q.append((nxt, mutations + 1))

        return -1

Time complexity: \(O(BL^2)\) with Python string construction, where \(B\) is the bank size and \(L\) is the gene length. Since \(L=8\), this is effectively \(O(B)\).

Space complexity: \(O(B)\) auxiliary space.

Comment on my solution

  • Bidirectional BFS is a strong and efficient approach.
  • The frontier-size swap correctly expands the smaller side.
  • Removing discovered genes prevents revisits.
  • There is one edge-case bug: startGene == endGene should be checked before requiring endGene to be in bank; the starting gene is valid even when absent from the bank.
  • Given bank.length <= 10, ordinary BFS is simpler and equally suitable for an interview answer.
# Ideas:
# - BFS with 2 frontiers
#   - for each word in front (or back), produce a candidate by modifying
#     an authorized letter, if valid, check if in back (or front) and
#     return the count, else add it to next front
#

# WORKS
class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        genes = set(bank)

        if endGene not in genes:
            return -1
        if startGene == endGene:
            return 0

        front = {startGene}
        back = {endGene}
        genes.discard(startGene)
        genes.discard(endGene)

        alphabet = {"A", "C", "G", "T"}

        mutations = 0

        while front:
            mutations += 1
            if len(front) > len(back):
                front, back = back, front

            next_front = set()

            for gene in front:
                for i, ch in enumerate(gene):
                    for letter in alphabet:
                        if letter == ch:
                            continue
                        mutation = gene[:i] + letter + gene[i+1:]
                        if mutation in back:
                            return mutations
                        if mutation in genes:
                            genes.discard(mutation)
                            next_front.add(mutation)

            front = next_front

        return -1

Extra

Why using ordinary BFS and not bidirectional BFS in this case

Can you expand a little bit on this: "Given bank.length <= 10, ordinary BFS is simpler and equally suitable for an interview answer."?

When Bidirectional BFS approach becomes necessary?

With bank.length <= 10, the graph contains at most:

  • One starting node.
  • Ten bank genes.
  • Twenty-four possible mutations checked per node: eight positions times three alternative letters.

Ordinary BFS therefore examines at most about \(11 \times 24\) candidate mutations. That is effectively trivial. Bidirectional BFS may inspect fewer nodes, but the savings are negligible compared with its extra bookkeeping and greater risk of subtle bugs.

In an interview, the usual preference is:

  • Start with the simplest algorithm that comfortably satisfies the constraints.
  • Introduce a more complex optimization only when the input size justifies it.

When bidirectional BFS matters

Suppose the shortest path has length \(d\) and each node has roughly \(b\) neighbors.

Ordinary BFS explores approximately:

\[ O(b^d) \]

Bidirectional BFS searches from both ends until the searches meet, exploring approximately:

\[ O(b^{d/2} + b^{d/2}) = O(b^{d/2}) \]

For example, with branching factor \(10\) and path length \(8\):

  • Ordinary BFS may explore around \(10^8\) states.
  • Bidirectional BFS may explore around \(2 \times 10^4\) states.

This exponential reduction can be decisive.

Good conditions for bidirectional BFS

It is especially useful when:

  • The state space is very large.
  • The start and target are both known.
  • The expected shortest path is relatively deep.
  • Transitions can be generated efficiently in both directions.
  • Edges are undirected, or reverse transitions are easy to compute.
  • A one-sided BFS would exceed time or memory limits.

Typical examples include:

  • Word Ladder with a large dictionary.
  • Large lock-combination searches.
  • Transformation puzzles with reversible moves.
  • Shortest paths in huge implicit graphs.

When it is not worth it

It is usually unnecessary when:

  • The graph has only a few nodes, as here.
  • The solution is expected to be shallow.
  • Reverse transitions are difficult to generate.
  • One BFS already fits easily within the limits.
  • Implementation simplicity and reliability matter more than a tiny constant-factor improvement.

So your bidirectional BFS is algorithmically strong, but with only ten bank entries it solves a scaling problem that the stated constraints do not actually have. Ordinary BFS communicates the graph model more directly and has fewer correctness details to manage.