Alien Dictionary – Solution & Complexity

from heapq import heappop, heappush

def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for i in range(len(words) - 1):
        first = words[i]
        second = words[i + 1]
        if len(first) > len(second) and first.startswith(second):
            return ""

        for a, b in zip(first, second):
            if a == b:
                continue
            if b not in graph[a]:
                graph[a].add(b)
                indegree[b] += 1
            break

    heap: list[str] = []
    for char, degree in indegree.items():
        if degree == 0:
            heappush(heap, char)

    order: list[str] = []
    while heap:
        char = heappop(heap)
        order.append(char)
        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                heappush(heap, neighbor)

    return ''.join(order) if len(order) == len(indegree) else ''