import heapq

from typing import (
    List,
)

class Solution:
    """
    @param words: a list of words
    @return: a string which is correct order
    """
    def alien_order(self, words: List[str]) -> str:
        # Write your code here
        graph = self.build_graph(words)
        if not graph:
            return ""

        return self.topological_sort(graph)

    def build_graph(self, words):
        graph = {} # node: neighbors

        # init graph
        for word in words:
            for c in word:
                if c not in graph:
                    graph[c] = set()

        # add edges
        n = len(words)
        for i in range(n-1): # compare i, i+1
            max_compare_length = min(len(words[i]), len(words[i+1]))
            for j in range(max_compare_length):
                if words[i][j] != words[i+1][j]: # compare two words, if different [i]->[i+1]
                    graph[words[i][j]].add(words[i+1][j])
                    break # finish add edge

                if j == max_compare_length - 1: # already last word, but edge not found
                    # case: err, errt (next must be longer)
                    if len(words[i]) > len(words[i+1]): 
                        return None # error case, early return 

        return graph

    def topological_sort(self, graph): 
        # init indegree, all node = 0
        indegree = {
            node: 0 for node in graph
        }

        # calculate indegree
        for node in graph:
            for neighbor in graph[node]:
                indegree[neighbor] = indegree[neighbor] + 1

        # find 0 indegree
        heap = [node for node in graph if indegree[node] == 0]
        heapq.heapify(heap) # smallest in lexicographical order`

        # bfs - topological sorting
        ans_order = ""
        while heap:
            node = heapq.heappop(heap)
            ans_order += node
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    heapq.heappush(heap, neighbor)

        # if all nodes popped
        if len(ans_order) == len(graph):
            return ans_order

        return ""