class Solution {
 public:
  string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    vector<int> inDegree(26);
    buildGraph(graph, words, inDegree);
    return topology(graph, inDegree);
  }

 private:
  void buildGraph(unordered_map<char, unordered_set<char>>& graph,
                  const vector<string>& words, vector<int>& inDegree) {
    // create node for each character in each word
    for (const string& word : words)
      for (const char c : word)
        if (!graph.count(c))
          graph[c] = unordered_set<char>();

    for (int i = 1; i < words.size(); ++i) {
      const string& first = words[i - 1];
      const string& second = words[i];
      const int length = min(first.length(), second.length());
      for (int j = 0; j < length; ++j) {
        const char u = first[j];
        const char v = second[j];
        if (u != v) {
          if (!graph[u].count(v)) {
            graph[u].insert(v);
            ++inDegree[v - 'a'];
          }
          break;  // later characters' order are meaningless
        }
        // first = "ab", second = "a" -> invalid
        if (j == length - 1 && first.length() > second.length()) {
          graph.clear();
          return;
        }
      }
    }
  }

  string topology(unordered_map<char, unordered_set<char>>& graph,
                  vector<int>& inDegree) {
    string s;
    queue<char> q;

    for (const auto& [c, _] : graph)
      if (inDegree[c - 'a'] == 0)
        q.push(c);

    while (!q.empty()) {
      const char u = q.front();
      q.pop();
      s += u;
      for (const char v : graph[u])
        if (--inDegree[v - 'a'] == 0)
          q.push(v);
    }

    // words = ["z", "x", "y", "x"]
    return s.length() == graph.size() ? s : "";
  }
};

class Solution {
  public String alienOrder(String[] words) {
    Map<Character, Set<Character>> graph = new HashMap<>();
    int[] inDegree = new int[26];
    buildGraph(graph, words, inDegree);
    return topology(graph, inDegree);
  }

  private void buildGraph(Map<Character, Set<Character>> graph, String[] words, int[] inDegree) {
    // create node for each character in each word
    for (final String word : words)
      for (final char c : word.toCharArray())
        graph.putIfAbsent(c, new HashSet<>());

    for (int i = 1; i < words.length; ++i) {
      final String first = words[i - 1];
      final String second = words[i];
      final int length = Math.min(first.length(), second.length());
      for (int j = 0; j < length; ++j) {
        final char u = first.charAt(j);
        final char v = second.charAt(j);
        if (u != v) {
          if (!graph.get(u).contains(v)) {
            graph.get(u).add(v);
            ++inDegree[v - 'a'];
          }
          break; // later characters' order are meaningless
        }
        // first = "ab", second = "a" -> invalid
        if (j == length - 1 && first.length() > second.length()) {
          graph.clear();
          return;
        }
      }
    }
  }

  private String topology(Map<Character, Set<Character>> graph, int[] inDegree) {
    StringBuilder sb = new StringBuilder();
    Queue<Character> q = graph.keySet()
                             .stream()
                             .filter(c -> inDegree[c - 'a'] == 0)
                             .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      final char u = q.poll();
      sb.append(u);
      for (final char v : graph.get(u))
        if (--inDegree[v - 'a'] == 0)
          q.offer(v);
    }

    // words = ["z", "x", "y", "x"]
    return sb.length() == graph.size() ? sb.toString() : "";
  }
}

class Solution:
  def alienOrder(self, words: List[str]) -> str:
    graph = {}
    inDegree = [0] * 26

    self._buildGraph(graph, words, inDegree)
    return self._topology(graph, inDegree)

  def _buildGraph(self, graph: Dict[chr, Set[chr]], words: List[str], inDegree: List[int]) -> None:
    # create node for each character in each word
    for word in words:
      for c in word:
        if c not in graph:
          graph[c] = set()

    for first, second in zip(words, words[1:]):
      length = min(len(first), len(second))
      for j in range(length):
        u = first[j]
        v = second[j]
        if u != v:
          if v not in graph[u]:
            graph[u].add(v)
            inDegree[ord(v) - ord('a')] += 1
          break  # later characters' order are meaningless
        # first = 'ab', second = 'a' . invalid
        if j == length - 1 and len(first) > len(second):
          graph.clear()
          return

  def _topology(self, graph: Dict[chr, Set[chr]], inDegree: List[int]) -> str:
    s = ''
    q = deque()

    for c in graph:
      if inDegree[ord(c) - ord('a')] == 0:
        q.append(c)

    while q:
      u = q.pop()
      s += u
      for v in graph[u]:
        inDegree[ord(v) - ord('a')] -= 1
        if inDegree[ord(v) - ord('a')] == 0:
          q.append(v)

    # words = ['z', 'x', 'y', 'x']
    return s if len(s) == len(graph) else ''