Minimum Genetic Mutation via BFS Graph Traversal

Graph Playlist Architecture:
- The graph study series is organized into two separate playlists, mirroring the structure of dynamic programming courses:
1. Foundational Graph Playlist: Covers standard graph representations, graph terminology, and core traversal techniques including Breadth-First Search (BFS) and Depth-First Search (DFS).
2. Advanced Graph Problem-Solving Playlist: Dedicated exclusively to solving high-frequency interview problems using optimal patterns explained in an accessible step-by-step manner.
Pedagogical Objective:
- Graph topics often cause apprehension among students due to state-space complexity. Structuring problems by concrete structural patterns—such as unweighted shortest path exploration via BFS—makes state transformations intuitive and systematic.

Mapping Strings to Graph Nodes:
- Problems requiring the transformation of a start string into an end string through sequential character replacements are implicitly graph problems.
- Vertices (Nodes): Each valid string configuration represents a vertex in a implicit state-space graph.
- Edges: An undirected edge exists between two string nodes if and only if one string can be converted into the other via a single valid character substitution.
- Edge Weights: Every valid single-character substitution represents a step cost of $1$ .
Optimal Traversal Selection:
- Because all edge weights are uniform ( $1$ step per mutation), finding the minimum number of transformations to reach the target string corresponds directly to finding the shortest path in an unweighted graph.
- Breadth-First Search (BFS) is uniquely suited for this task because it explores the state space level-by-level, guaranteeing that the first time the target string is reached, the path taken uses the minimum possible number of edges/steps.

Input Parameters:
- start: A string representing the initial gene sequence (e.g., an $8$ -character string).
- end: A string representing the target gene sequence to reach.
- bank: A collection of valid gene strings (std::vector<std::string> bank).
Permitted Alphabet:
- Gene sequences consist only of characters from the set {'A', 'C', 'G', 'T'}.
Required Output:
- An integer representing the minimum number of mutation steps needed to transform start into end.
- If the target end string cannot be reached via valid intermediate mutations present in bank, the program must return $-1$ .

Single-Character Mutation Rule: Exactly one character can be altered per step.
Bank Validity Constraint: A mutated sequence is considered valid if and only if it exists in the provided bank array.
Visited State Constraint: A string sequence that has already been explored must never be processed again to avoid infinite loops and cycles (e.g., oscillating back and forth between two valid gene states).
Shortest Path Property: Level-order processing ensures that the state distance $k$ at Level $k$ is minimal.

Level-Order Exploration Model:
- Level $0$ : Contains the start string.
- Level $1$ : Contains all valid, unvisited single-character gene mutations reachable directly from start that exist in bank.
- Level $k$ : Contains all valid, unvisited gene mutations reachable by one substitution from nodes at Level $k-1$ .
Exploration Loop Algorithm:
1. Determine the size of the queue n = q.size() at the start of processing a level.
2. Process all n nodes of the current level.
3. For each popped string, iterate through every character index $i \text{ from } 0 \text{ to } L-1$ (where $L$ is string length).
4. Substitute index $i$ with each character in {'A', 'C', 'G', 'T'}.
5. Check if the generated string equals end. If true, immediately return level (or level + 1 depending on evaluation timing).
6. If the mutated string is present in bank and not in visited, mark it as visited and push it to the queue.
7. Increment level by $1$ after processing all n elements of the current level.