433. Minimum Genetic Mutation

📝 Problem Details

• Title: 433. Minimum Genetic Mutation
• Link: https://leetcode.com/problems/minimum-genetic-mutation/
• Difficulty: Medium
• Tags/Categories: BFS Queue Hashmap Strings

💭What Were My Initial Thoughts?

use of a hashmap to store char values and a vector of all index retaining to that mutation value
(not correct)

🤔What Did I Struggle With?

Was unable to come up with the graph interpretation

Intuition for BFS:

1. Problem Representation:

• each gene (string) can be seen as a node
• a valid single-char mutation transforms one gene into another, forming an edge between two nodes
• the task is to find the shortest path from the startGene to the endGene through this graph, where the valid genes are in the bank

2. Layered Exploration:

• BFS explores all nodes (mutations) at the same “distance” (i.e. single mutation steps) before moving to nodes further away.
• This ensures that when you reach endGene, you’ve found the shortest path possible

3. Efficiency / Optimization:

• BFS avoids revisiting already-explored genes (nodes), reducing redundant computation
• By storing valid genes in a set (or hashmap), we can quickly check if a gene is part of the bank

💡 Explanation of Solution

BFS Approach:

1. init
	- create a queue of pairs, starting with the startGene and an initial mutation count of 0
	- create a set representation of genes in bank
	- create a set for visited to avoid redundant computation

2. iterative exploration
	- while the queue is not empty
		- deque the current gene and its mutation count 
		- for each character position in the current gene
			- replace the character with one of the three other possible characters [A, C, G, T]
			- generate a new gene (potential neighbour)
			- if the new gene matches endGene, return the mutation count + 1
			- if the new gene exists in the bank and has been visited:
				- mark it as visited
				- enqueue the new gene with the updated mutation count

3. termination
	- if the queue is empty and endGene hasn't been reached, return -1 (no valid mutation path exists)

⌛ Complexity Analysis

Time Complexity: O(n)
- constant string length (8), which keeps the number of mutations per node bounded 
- efficient O(1) lookups for validation using set
- n represents the number of elements in bank

Space Complexity: O(n)
- visited set stores up to n nodes
- queue stores nodes to be processed, worst case of n nodes in the queue
- bank set stores n elements

💻 Implementation of Solution

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        // Convert the bank into an unordered_set for O(1) lookups
        unordered_set<string> geneBank(bank.begin(), bank.end());
        
        // If endGene is not in the bank, return -1 immediately
        if (geneBank.find(endGene) == geneBank.end()) {
            return -1;
        }
        
        // BFS setup
        queue<pair<string, int>> q; // Pair of current gene and mutation count
        q.push({startGene, 0});
        unordered_set<string> visited; // To avoid revisiting genes
        visited.insert(startGene);
        
        // Possible mutations for each character
        const char mutations[] = {'A', 'C', 'G', 'T'};
        
        // BFS loop
        while (!q.empty()) {
            auto [currentGene, mutationsCount] = q.front();
            q.pop();
            
            // Try mutating each character of the current gene
            for (int i = 0; i < currentGene.size(); ++i) {
                char originalChar = currentGene[i];
                for (char mutation : mutations) {
                    if (mutation == originalChar) continue;
                    
                    // Generate a new gene by mutating one character
                    currentGene[i] = mutation;
                    
                    // If the new gene matches the endGene, return the result
                    if (currentGene == endGene) {
                        return mutationsCount + 1;
                    }
                    
                    // If the new gene is valid and not visited, enqueue it
                    if (geneBank.find(currentGene) != geneBank.end() && visited.find(currentGene) == visited.end()) {
                        visited.insert(currentGene);
                        q.push({currentGene, mutationsCount + 1});
                    }
                }
                // Revert the change to try other mutations
                currentGene[i] = originalChar;
            }
        }
        
        // If we exhaust all possibilities without finding the endGene
        return -1;
    }
};