Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Minimum Genetic Mutation (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You have a gene sequence represented by an 8-character string, containing only 'A', 'C', 'G', or 'T' characters. To change from one gene sequence to another, you can mutate one character at a time.

For example, "AAAAACCC" --> "AAAACCCC" is one mutation.

Each intermediate sequence must be a valid gene in the provided list (bank).

The gene bank bank 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, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

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

Examples

Example 1:

  • Input: startGene: "AACCGGTT", endGene: "AAACGGTA", bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
  • Expected Output: 2
  • Justification:
    • Mutations: "AACCGGTT" → "AACCGGTA" → "AAACGGTA"

Example 2:

  • Input: startGene: "AAAAACCC", endGene: "AACCCCCC", bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
  • Expected Output: 3
  • Justification:
    • Mutations: "AAAAACCC" → "AAAACCCC" → "AAACCCCC" → "AACCCCCC"

Example 3:

  • Input: startGene: "AACCGGTT", endGene: "CCGGTTAA", bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA", "CCGGTTAA"]
  • Expected Output: -1
  • Justification: We need to mutate a total of 8 characters, but the 'bank' array contains only 4 strings. So, it is not possible to perform 8 mutations.

Try it yourself

Try solving this question here:

Python3
Python3

. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible