There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this new language.
Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return ” “. If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if, at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example 1:

Input: Words: ["ba", "bc", "ac", "cab"]
Output: bac
Explanation: Given that the words are sorted lexicographically by the rules of the alien language, so
from the given words we can conclude the following ordering among its characters:
 
1. From "ba" and "bc", we can conclude that 'a' comes before 'c'.
2. From "bc" and "ac", we can conclude that 'b' comes before 'a'
 
From the above two points, we can conclude that the correct character order is: "bac"

Example 2:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 3:

Input: words = ["z","x"]
Output: "zx"

Code:

import java.util.*;
import java.io.*;

class Innoskrit {

    public String alienOrder(String[] words) {
        if(words == null || words.length == 0) {
			return "";
		}

		StringBuilder sortedOrder = new StringBuilder();
		HashMap<Character, Integer> inDegree = new HashMap<>();
		HashMap<Character, ArrayList<Character>> graph = new HashMap<>();

		for(String word : words) {
			for(char ch : word.toCharArray()) {
				inDegree.put(ch, 0);
				graph.put(ch, new ArrayList<>());
			}
		}

		for(int i = 0; i < words.length - 1; i++) {
			String word1 = words[i];
			String word2 = words[i + 1];
            if(word2.length() < word1.length() && word1.startsWith(word2)) {
                return "";
            }
			for(int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
				char parent = word1.charAt(j);
				char child = word2.charAt(j);
				if(parent != child) {
					graph.get(parent).add(child);
                    inDegree.put(child, inDegree.get(child) + 1);
					break;
				}
			}
		}

		// processing all valid starting nodes
		Queue<Character> queue = new LinkedList<>();
		for(Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
			if(entry.getValue() == 0) {
				queue.offer(entry.getKey());
			}
		}

		while(!queue.isEmpty()) {
			char vertex = queue.poll();
			sortedOrder.append(vertex);
			ArrayList<Character> children = graph.get(vertex);
			for(char child : children) {
				inDegree.put(child, inDegree.get(child) - 1);
				if(inDegree.get(child) == 0) {
					queue.offer(child);
				}
			}
		}

		if(sortedOrder.length() != inDegree.size()) {
			return "";
		}

		return sortedOrder.toString();
    }

	public static void main(String[] args) {
	    Innoskrit obj = new Innoskrit();
		String words[] = {"ywx", "wz", "xww", "xz", "zyy", "zwz"};
		String languageOrder = obj.alienOrder(words);
		System.out.println(languageOrder);
	}
}

from collections import deque

class Innoskrit:
    def alienOrder(self, words):
        if len(words) == 0:
            return ""

        in_degree = {}
        graph = {}

        for word in words:
            for char in word:
                in_degree[char] = 0
                graph[char] = []

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            if len(w2) < len(w1) and w1.startswith(w2):
                return ""
            for j in range(min(len(w1), len(w2))):
                parent, child = w1[j], w2[j]
                if parent != child:
                    graph[parent].append(child)
                    in_degree[child] += 1
                    break

        queue = deque()
        for key in in_degree:
            if in_degree[key] == 0:
                queue.append(key)

        sorted_order = []
        while queue:
            vertex = queue.popleft()
            sorted_order.append(vertex)
            for child in graph[vertex]:
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    queue.append(child)

        if len(sorted_order) != len(in_degree):
            return ""

        return ''.join(sorted_order)

if __name__ == '__main__':
    obj = Innoskrit()
    words = ["ywx", "wz", "xww", "xz", "zyy", "zwz"]
    ans = obj.alienOrder(words)
    print(ans)