class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> bankSet(bank.begin(), bank.end());
        unordered_set<string> seen;
        queue<string> que;

        int level = 0;
        que.push(startGene);
        seen.insert(startGene);

        while(!que.empty()) {
            int size = que.size();

            // use level order traversal
            for(int i = 0; i < size; i++) {
                string currGene = que.front();
                que.pop();

                // if currGene is equal to endGene, return step
                if(currGene == endGene) return level;

                for(char c : "ATCG") {
                    for(int i = 0; i < 8; i++) {
                        string updateGene = currGene;
                        // only update a character
                        updateGene[i] = c;

                        // if we visit the gene before, we should not visit again
                        if(bankSet.count(updateGene) == 1 && seen.count(updateGene) == 0) {
                            que.push(updateGene);
                            seen.insert(updateGene);
                        }
                    }
                }
            }

            level++;
        }

        // if no gene is equal to endGene, return -1
        return -1;
    }
};