Rakesh Reddy Peddamallu

Posted on Aug 7

Leetcode - 433. Minimum Genetic Mutation

#leetcode

🔍 Problem Overview

Imagine you’re playing a game where you can mutate genes by changing one character at a time. But there's a catch — each mutation must be a valid gene, and all valid genes are given in a list called the bank.

You're given:

startGene: your starting DNA sequence (e.g., "AACCGGTT")
endGene: your target DNA sequence (e.g., "AAACGGTA")
bank: a list of valid gene strings

Each gene is 8 characters long and only contains the letters 'A', 'C', 'G', and 'T'.

Your goal: Find the minimum number of mutations needed to reach endGene from startGene, using only valid intermediate steps from the bank. If it's not possible, return -1.

🚀 Real-world Analogy

It's like solving a word ladder:

Start with a word (AACCGGTT)
Change one letter at a time
Each step must be a valid word (from the bank)
End with the goal word (AAACGGTA)

👨‍🔬 Strategy: Breadth-First Search (BFS)

Since we’re looking for the shortest number of steps, BFS is the perfect tool.

Why BFS?

Each level of BFS = 1 mutation
As soon as we reach the endGene, we know it's the shortest path

🛠️ Step-by-Step BFS Plan

Put the startGene into a queue along with a step counter (0).
Use a Set to store valid genes from the bank for O(1) lookup.
For each gene in the queue:

Try mutating each position (0 to 7) with 'A', 'C', 'G', 'T'.
If the mutated gene is in the bank and not yet visited:
- Add it to the queue for further exploration.
  1. Keep doing this until you find the endGene.
  2. If the queue is empty and you haven’t found it, return -1.

🧬 Code Explanation

var minMutation = function(startGene, endGene, bank) {
    const geneBank = new Set(bank);
    if (!geneBank.has(endGene)) return -1; // Can't reach endGene

    const queue = [[startGene, 0]];
    const visited = new Set();
    const genes = ['A', 'C', 'G', 'T'];

    while (queue.length > 0) {
        const [current, steps] = queue.shift();

        if (current === endGene) return steps;

        for (let i = 0; i < current.length; i++) {
            for (let geneChar of genes) {
                if (geneChar === current[i]) continue;

                // 👇 Key mutation line explained below
                const mutated = current.slice(0, i) + geneChar + current.slice(i + 1);

                if (geneBank.has(mutated) && !visited.has(mutated)) {
                    visited.add(mutated);
                    queue.push([mutated, steps + 1]);
                }
            }
        }
    }

    return -1;
};

🔍 Detailed Breakdown: Mutation Line

const mutated = current.slice(0, i) + geneChar + current.slice(i + 1);

What it does:

Replaces the character at index i in the string current with geneChar.

Example:

Let’s say:

current = "AACCGGTT"
i = 2
geneChar = "T"

Break it into 3 parts:

current.slice(0, i) → "AA" (characters before index 2)
geneChar → "T" (our new character)
current.slice(i + 1) → "CGGTT" (characters after index 2)

So:

mutated = "AA" + "T" + "CGGTT" = "AATCGGTT"

Why this is great:

Strings in JavaScript are immutable. You can’t change characters directly.
This trick uses slice() to surgically replace a character in one line.

🧠 Time & Space Complexity

Time Complexity:

O(M × N × 4)
Where:

M = number of genes in the bank
N = length of each gene (always 8)
4 = number of possible mutations at each character (A, C, G, T)

Because for every gene, we try changing every character in 4 ways.

Space Complexity:

O(M)

For the visited set
For the BFS queue
And the bank set

✅ Sample Run

minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA","AACCGCTA","AAACGGTA"]);
// Returns 2

// Path: AACCGGTT → AACCGGTA → AAACGGTA

🧠 Final Thoughts

This is a fantastic problem to practice BFS with string mutation. The clever use of slice() to mutate characters is a common technique in string transformation problems.

🧬 Tip: Whenever you need to transform strings one character at a time, think of using slice(0, i) + newChar + slice(i + 1) as your go-to trick.

DEV Community