Minimum Genetic Mutation

To solve the Minimum Genetic Mutation problem efficiently, I would treat this as a shortest path problem on an unweighted graph. Since we need the minimum number of mutations, Breadth-First Search is the optimal approach because it explores all neighbors at the current depth before moving deeper, ensuring the first time we reach the target gene, it is via the shortest path. My implementation would start by initializing a queue with the starting gene and a mutation count of zero. I would also convert the input bank into a hash set for constant-time validation. In the main loop, I dequeue the current gene, generate all possible next states by changing each character to 'A', 'C', 'G', or 'T', and check if these new strings exist in our bank set. If a generated string matches the end gene, I immediately return the current step count plus one. If it exists in the bank but isn't the target, I add it to the queue and remove it from the set to mark it as visited, preventing cycles. This ensures we explore the search space level by level. If the queue empties without finding the end gene, I return -1. This approach yields a time complexity of O(N * M), where N is the gene length and M is the bank size, which is highly performant for Google's scale requirements.