class Solution {
    public String foreignDictionary(String[] words) {      
        Map> adjMap = new HashMap<>();
        Map indegree = new HashMap<>();
        // init adjacency list with unique nodes(letters)
        for(String w: words) {
            for(Character c: w.toCharArray()) {
                adjMap.putIfAbsent(c, new HashSet<>());
                indegree.putIfAbsent(c, 0);
            }
        }
        // fill the adjacency list i.e build the dependencies
        for(int i=1; i word2.length()) {
                return "";
            }

            // find the first non-matching letter
            int x = 0;
            while(x < Math.min(word1.length(), word2.length())) {
                Character u = word1.charAt(x);
                Character v = word2.charAt(x);
                if(u != v) {
                    // add edge from u -> v
                    adjMap.get(u).add(v);
                    // opt: you can build indegree here itself
                    break;
                }
                x++;
            }
        }
        // adjacency list is ready to be parsed. apply topo sort now
        
        // calculate indegrees
        

        for(Character u: adjMap.keySet()) {
            for(Character v: adjMap.get(u)) {
                int curDegree = indegree.getOrDefault(v, 0);
                indegree.put(v, curDegree+1);
            }
        }

        System.out.println(indegree);


        Queue q = new LinkedList<>();
        // enqueue nodes with indegree=0
        for(Character c: indegree.keySet()) {
            if(indegree.get(c) == 0) {
                q.add(c);
            }
        }

        List res = new ArrayList<>(); // note that this in in reverse dictionary order
        while(!q.isEmpty()) {
            Character cur = q.poll();
            res.add(cur);
            
            // relax the indegrees of the neighbours
            for(Character nei: adjMap.get(cur)) {
                indegree.put(nei, indegree.get(nei) - 1);
                if(indegree.get(nei) == 0) {
                    q.add(nei);
                }
            }
        }

        // you can't make indegree for some, hence cycle
        if(res.size() != adjMap.size()) return "";

        StringBuilder resString = new StringBuilder(res.size());
        for(Character r: res) {
            resString.append(r);
        }

        return resString.toString();

    }
}