Minimum Genetic Mutation

MediumGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A gene is an 8-character string made only of the letters 'A', 'C', 'G', and 'T'. A single **mutation** changes exactly one character of the gene to a different letter. You are given startGene, endGene, and a list bank of valid genes. Every gene produced along the way (including endGene) must appear in bank; startGene itself does not need to be in bank. Return the minimum number of mutations to turn startGene into endGene, or -1 if it cannot be done. If startGene already equals endGene, return 0.

Examples

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
One mutation changes the last `T` to `A`, and the result is in the bank.
Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
`AACCGGTT -> AACCGGTA -> AAACGGTA` takes 2 mutations, and `endGene` differs from `startGene` in two positions, so 1 mutation is not enough.

Constraints

  • 0 <= bank.length <= 10
  • `startGene.length == endGene.length == bank[i].length == 8`
  • All strings contain only `A`, `C`, `G`, `T`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems