ALIEN_DICTIONARY

class Solution {
public:
    unordered_map<char, vector<char>> adj;
    set<char> s;
    unordered_map<char, int> color;
    unordered_map<char, int> vis;

    bool detectCycle(char itr) {
        color[itr] = 1; // being visited

        for(auto c: adj[itr]) {
            if(color[c] == 1) {
                return true; // backedge
            }

            if(color[c] == 0 and detectCycle(c)) {
                return true; //self - loop
            }
        }
        color[itr] = 2; // processed

        return false;
    }


    void topo(stack<char> &st, char itr) {
        vis[itr] = true;

        for(char c: adj[itr]) {
            if(!vis[c]) {
                topo(st, c);
            }
        }
        st.push(itr);
    }

    string alienOrder(vector<string>& W) {
        int n = W.size();

        //construcitng a graph for performing topo sort

        for(string str: W) {
            for(char c: str) {
                s.insert(c);
                color[c] = 0;
            }
        }

        for(int i = 0; i < n - 1; ++i) {
            int min_len = min(W[i].size(),W[i + 1].size());


            if(W[i].size() > W[i + 1].size() and W[i].substr(0,min_len) == W[i + 1].substr(0,min_len)) {
                return "";
            }

            for(int j = 0; j < min_len; ++j) {
                if(W[i][j] != W[i + 1][j]) {
                    adj[W[i][j]].push_back(W[i + 1][j]);
                    break;
                }
            }
        }


        // for(auto c: adj) {
        //     cout << c.first << " ";
        //     for(auto cc: c.second) {
        //         cout << cc << " ";
        //     }
        //     cout << "\n";
        // }


        //graph has been constructed, now do topo sort

        //first check if it has a cycle

        //if not then order the vertices in a usual topo manner


        // vertices will be in s
        // 0 --- unvisited
        // 1 ---- being visited
        // 2 ------ visited and processes
        for(auto it : s) {
            vis[it] = 0;
            if(color[it] == 0) {
                if(detectCycle(it)) {
                    return "";
                }
            }
        }

        stack<char> st;


        for(auto it : s) {
            if(vis[it] == 0) {
                topo(st,it);
            }
        }

        string ans = "";

        while(!st.empty()) {
            ans += st.top();
            st.pop();
        }


        return ans;

    }
};