Minimum Genetic Mutation
A gene is represented by a string of 8 characters.
Each character can be one of:
A
C
G
T
You are given:
- startGene
- endGene
- bank containing valid gene strings
A mutation changes exactly one character of the current gene.
Every intermediate gene must exist in the given bank.
Return the minimum number of mutations needed to transform startGene into endGene.
If it is impossible, return:
-1
Example
startGene = "AACCGGTT"
endGene = "AACCGGTA"
bank =
["AACCGGTA"]
We can change:
AACCGGTT
↓
AACCGGTA
Only one character changes.
Therefore:
1
Main Idea
This is a BFS + HashSet problem.
Each valid gene can be treated as a graph node.
Two genes are connected if they differ by exactly one character.
For every current gene:
- Try changing each of its 8 characters.
Try all four possible characters:
A, C, G, T
- If the resulting gene exists in bank and has not been visited, add it to the BFS queue.
- The first time we reach endGene, return the number of mutations.
Since every mutation costs exactly 1, BFS gives the minimum number of mutations.
Example 1
Input
AACCGGTT AACCGGTA 1 AACCGGTA
Output
1
Explanation
Only the last character changes:
AACCGGTT
↓
AACCGGTA
So the minimum number of mutations is:
1
Example 2
Input
AACCGGTT AAACGGTA 5 AACCGGTA AACCGCTA AAACGGTA AACCGGAA AACCGCAA
Output
2
Explanation
One valid mutation sequence is:
AACCGGTT
↓
AACCGGTA
↓
AAACGGTA
Two characters are changed, one at a time.
Therefore:
2
Constraints
Hints:
Hint 1
A mutation changes exactly one character.
Follow-up
For each position, try replacing the character with:
A
C
G
T
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 17, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output