"""
There is a foreign language which uses the latin alphabet, but the order among letters is not "a", "b", "c" ... "z" as in English.

You receive a list of non-empty strings words from the dictionary, where the words are sorted lexicographically based on the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them.

A string a is lexicographically smaller than a string b if either of the following is true:

    The first letter where they differ is smaller in a than in b.
    a is a prefix of b and a.length < b.length.

Example 1:

Input: ["z","o"]

Output: "zo"

Explanation:
From "z" and "o", we know 'z' < 'o', so return "zo".

Example 2:

Input: ["hrn","hrf","er","enn","rfnn"]

Output: "hernf"

Explanation:

    from "hrn" and "hrf", we know 'n' < 'f'
    from "hrf" and "er", we know 'h' < 'e'
    from "er" and "enn", we know 'r' < 'n'
    from "enn" and "rfnn" we know 'e' < 'r'
    so one possible solution is "hernf"

Constraints:

    The input words will contain characters only from lowercase 'a' to 'z'.
    1 <= words.length <= 100
    1 <= words[i].length <= 100
"""

from collections import defaultdict, deque
from collections.abc import Iterator


def gen_dependencies(inputs: list[str]) -> Iterator[tuple[str, str]]:
    for a, b in zip(inputs, inputs[1:]):
        # Find the first different character, to yield the dependency
        for x, y in zip(a, b):
            if x != y:
                yield (x, y)
                break
        else:
            if len(a) > len(b):
                raise ValueError("Invalid dictionary")


def dfs(graph):
    visited = defaultdict(int)  # 0: not visited, -1: visiting, 1: visited.
    deps = deque()
    if all(do_dfs(graph, visited, v, deps) for v in graph):
        return deps
    else:
        raise ValueError("Cycle detected")


def do_dfs(graph, visited, v, deps):
    if visited[v] == -1:
        return False  # cycle detected

    if visited[v] == 1:
        return True  # visited already

    visited[v] = -1
    if all(do_dfs(graph, visited, n, deps) for n in graph.get(v, [])):
        visited[v] = 1
        # All dependencies are resolved, add v
        deps.append(v)
        return True
    return False


def main(words: list[str]):
    graph = defaultdict(list)
    try:
        for x, y in set(gen_dependencies(words)):
            # x precedes y, so y depends on x
            graph[y].append(x)

        for x in set(x for word in words for x in word):
            if x not in graph:
                graph[x] = []

        # apply the dfs
        deps = dfs(graph)
        return "".join(deps)
    except ValueError:
        return ""


if __name__ == "__main__":
    assert main(["hrn", "hrf", "er", "enn", "rfnn"]) == "hernf"
    assert main(["wrtkj", "wrt"]) == ""