Alien Dictionary

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.

• Time : O(n * maxlength(s) + k)
• Space : O(k)

c++

class Solution{
    pair<char, char> order(string& a, string& b) {
        int i = 0, j = 0, n = a.length(), m = b.length();
        while(i < n and j < m) {
            if(a[i] == b[j]) i++,j++;
            else return {a[i], b[j]};
        }
        return {'#', '#'};
    }
public:
    string findOrder(string dict[], int N, int K) {
        unordered_map<char, int> ind;
        unordered_map<char, vector<char>> adj;
        for(int i = 0; i < N - 1; i++) {
            pair<char, char> p = order(dict[i], dict[i + 1]);
            char front = p.first, back = p.second;
            if(front == '#') continue;
            ind[back] += 1;
            ind[front] += 0;
            adj[front].push_back(back);
        }
        queue<char> q;
        string res = "";
        for(auto& p : ind) {
            char ch = p.first;
            int deg = p.second;
            if(deg) continue;
            q.push(ch);
            res.push_back(ch);
        }
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(--ind[v] == 0) {
                    q.push(v);
                    res.push_back(v);
                }
            }
        }
        return res;
    }
};