Command Palette

Search for a command to run...

Hectal
Problem 42.4 · Pattern Recognition DrillsMedium

Minimum Genetic Mutation

What it teaches:

Practise it on judges as “Minimum Genetic Mutation”.

In plain words

Think of each allowed gene as a stepping stone, and two stones are joined if they differ in exactly one letter. You want the fewest hops from the start stone to the end stone. Explore in rings: first every stone one hop away, then every stone two hops away, and so on. The first ring that contains the end gives the answer.

Return the fewest mutations, or −1 if the end can't be reached. Example: start = AACCGGTT, end = AAACGGTA, bank = [AACCGGTA, AACCGCTA, AAACGGTA] → 2.

The problem

Genes are 8-character strings over A, C, G, T. One mutation changes one character, and every intermediate gene must be in bank. Return the fewest mutations from startGene to endGene, or −1.

Example 1

Input: start = AACCGGTT, end = AAACGGTA, bank = [AACCGGTA, AACCGCTA, AAACGGTA]
Output: 2

Constraints

  • 0 ≤ bank ≤ 10

Pattern clues in the wording

  • → Fewest steps
  • → One change at a time
  • → Allowed states listed

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        return -1;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
startGene = "AACCGGTT"
endGene = "AACCGGTA"
bank = ["AACCGGTA"]
1
2
startGene = "AACCGGTT"
endGene = "AAACGGTA"
bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
2

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. BFS over genes · O(bank × 8 × 4)
1

BFS over genes

Time O(bank × 8 × 4) Space O(bank)

Level-order BFS; try 8 positions × 4 letters; keep only bank genes not yet visited.

▶ Dry run: Rings of one-letter changesstart = AACCGGTT, end = AAACGGTA, bank = [AACCGGTA, AACCGCTA, AAACGGTA]
AACCGGTTAACCGGTAAAACGGTAAACCGCTA

queue(queue)

AACCGGTT

steps(vars)

0

Step 1/4Start with the start gene at 0 steps. It is not the end.

Approach 1
import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> valid = new HashSet<>(Arrays.asList(bank));
        if (!valid.contains(endGene)) return -1;
        Deque<String> q = new ArrayDeque<>(List.of(startGene));
        Set<String> seen = new HashSet<>(List.of(startGene));
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int size = q.size(); size > 0; size--) {
                String g = q.poll();
                if (g.equals(endGene)) return steps;
                char[] c = g.toCharArray();
                for (int i = 0; i < c.length; i++) {
                    char orig = c[i];
                    for (char ch : new char[]{'A', 'C', 'G', 'T'}) {
                        c[i] = ch;
                        String t = new String(c);
                        if (valid.contains(t) && seen.add(t)) q.offer(t);
                    }
                    c[i] = orig;
                }
            }
        }
        return -1;
    }
}

Verdict: Word Ladder with a tiny alphabet.

Before you submit

Edge cases and common mistakes

Test these inputs

  • End not in the bank
  • Start equals end (0)

Mistakes people make

  • DFS (finds a path, not the shortest).

Interview

Follow-up questions

Which other course problem is this?