269. Alien Dictionary

class Solution {
    public String alienOrder(String[] words) {
        int[] f = new int[26];
        Arrays.fill(f, -1);
        int distinct = 0;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(String w : words)
        {
            for(char ch : w.toCharArray())
            {
                int idx = ch - 'a';
                if(f[idx] < 0)
                {
                    f[idx] = 0;
                    distinct++;
                    map.put(idx, new HashSet<>());
                }
            }
        }
        int n = words.length;
        for(int i = 0; i < n - 1; i++)
        {
            String a = words[i], b = words[i + 1];
            int l1 = a.length(), l2 = b.length(), len = Math.min(l1, l2);
            if(a.equals(b)) continue;
            int j = 0;
            while(j < len && a.charAt(j) == b.charAt(j)) j++;
            if(j == len) continue;   // case 'aa' and 'aaa' does not tell any information
            // now i is the different character position
            int idx0 = a.charAt(j) - 'a', idx1 = b.charAt(j) - 'a';
            if(map.get(idx0).contains(idx1)) continue;
            map.get(idx0).add(idx1);
            f[idx1]++;
        }
        // System.out.println(map);
        // System.out.println(Arrays.toString(f));
        Queue<Integer> q = new LinkedList<>();
        int[] re = new int[distinct];
        int idx = 0;
        for(int i = 0; i < 26; i++)
        {
            if(f[i] == 0) q.offer(i);
        }
        while(!q.isEmpty())
        {
            int from = q.poll();
            re[idx++] = from;
            for(int to : map.get(from))
            {
                f[to]--;
                if(f[to] == 0) q.offer(to);
            }
        }
        if(idx < distinct) return "";
        StringBuilder sb = new StringBuilder();
        for(int k : re) sb.append((char)('a' + k));
        return sb.toString();
    }
}