class Solution {
    public String alienOrder(String[] words) {

        int maxLength = getMaxLength(words);
        Map<Character, List<Character>> graph = buildGraph(maxLength, words);
        List<Character> result = new ArrayList<>();
        Set<Character> visited = new HashSet<>();
        Set<Character> visiting = new HashSet<>();
        for(Character c: graph.keySet()) {
            if(!visited.contains(c)) {
                if(!topSort(graph, visiting, visited, c, result)) return "";
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Character c: result) {
            sb.append(c);
        }
        return sb.toString();
    }

    private int getMaxLength(String[] words) {
        Integer n = Integer.MIN_VALUE;
        for(String word: words) {
            n = Math.max(n, word.length());
        }
        return n;
    }

    private Map<Character, List<Character>> buildGraph(int maxLength, String[] words) {
        Map<Character, List<Character>> map = new HashMap<>();

        for(int i = 0;i<maxLength;i++) {
            Character prev = null;
            for(String word: words) {
                if(word.length()<=i) break;
                Character c = word.charAt(i);
                if(prev == null) {
                    prev = c;
                } else {
                    if(prev != c) {
                        map.putIfAbsent(prev, new ArrayList<>());
                        if(!map.get(prev).contains(c)) {
                            // only add if not contains, check required because of list
                            map.get(prev).add(c);
                        }

                    }
                    prev = c;
                }
            }
        }
        return map;
    }

    private boolean topSort(Map<Character, List<Character>> graph, Set<Character> visiting, Set<Character> visited, Character curr, List<Character> result) {

        if(visiting.contains(curr)) return false;

        visiting.add(curr);
        if(!graph.containsKey(curr)) return true;
        for(Character neighbor: graph.get(curr)) {
            if(!topSort(graph, visiting, visited, neighbor, result)) return false;
        }
        visiting.remove(curr);
        visited.add(curr);
        result.add(curr);
        return true;
    }
}