Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.
 
Example 1:
Input: 
N = 5, K = 4
dict = {"baa","abcd","abca","cab","cad"}
Output:
1
Explanation:
Here order of characters is 
'b', 'd', 'a', 'c' Note that words are sorted 
and in the given language "baa" comes before 
"abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.
Example 2:
Input: 
N = 3, K = 3
dict = {"caa","aaa","aab"}
Output:
1
Explanation:
Here order of characters is
'c', 'a', 'b' Note that words are sorted
and in the given language "caa" comes before
"aaa", therefore 'c' is before 'a' in output.
Similarly we can find other orders.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function findOrder() which takes  the string array dict[], its size N and the integer K as input parameter and returns a string denoting the order of characters in the alien language.
Expected Time Complexity: O(N * |S| + K) , where |S| denotes maximum length.
Expected Space Compelxity: O(K)
Constraints:
1 ≤ N, M ≤ 300
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Graph algorithms

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N * |S| + K) , where |S| denotes maximum length.
Expected Auxiliary Space: O(K)

Starter code:
#User function Template for python3



class Solution:

    def findOrder(self,alien_dict, N, K):

    # code here



Solutions:
from collections import deque

class Solution:

	def findOrder(self, dict, N, K):
		adj = [[] for _ in range(K)]
		for i in range(N - 1):
			s1 = dict[i]
			s2 = dict[i + 1]
			n = min(len(s1), len(s2))
			for j in range(n):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		ind = [0] * K
		q = deque()
		for i in range(K):
			for it in adj[i]:
				ind[it] += 1
		for i in range(K):
			if ind[i] == 0:
				q.append(i)
		tpo = []
		while q:
			node = q.popleft()
			tpo.append(node)
			for child in adj[node]:
				ind[child] -= 1
				if ind[child] == 0:
					q.append(child)
		ans = ''
		for it in tpo:
			ans += chr(it + ord('a'))
		return ans


from collections import *

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		in_degree = {ch: 0 for word in alien_dict for ch in word}
		for i in range(N - 1):
			first_word = alien_dict[i]
			second_word = alien_dict[i + 1]
			small = min(len(first_word), len(second_word))
			for j in range(small):
				if first_word[j] != second_word[j]:
					graph[first_word[j]].append(second_word[j])
					in_degree[second_word[j]] += 1
					break
		arr = [ch for ch in in_degree if in_degree[ch] == 0]
		queue = deque(arr)
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for edge in graph[node]:
				in_degree[edge] -= 1
				if in_degree[edge] == 0:
					queue.append(edge)
		return ans


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		inDegree = {chr(i + 97): 0 for i in range(k)}
		i = 0
		while i < len(alien_dict) - 1:
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			n = min(len(word1), len(word2))
			j = 0
			while j < n:
				if word1[j] != word2[j]:
					graph[word1[j]].append(word2[j])
					inDegree[word2[j]] += 1
					break
				j += 1
			i += 1
		queue = deque()
		order = []
		for (key, val) in inDegree.items():
			if val == 0:
				queue.append(key)
		while queue:
			current = queue.popleft()
			order.append(current)
			for nei in graph[current]:
				inDegree[nei] -= 1
				if inDegree[nei] == 0:
					queue.append(nei)
		if len(order) != k:
			return 0
		return order


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		indegree = [0] * K
		stack = []
		queue = []
		adj = [[] for i in range(k)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			length = min(len(s1), len(s2))
			for j in range(length):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		for i in range(K):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(K):
			if indegree[i] == 0:
				queue.append(i)
		topo = []
		while queue:
			node = queue.pop(0)
			topo.append(chr(ord('a') + node))
			for child in adj[node]:
				indegree[child] = indegree[child] - 1
				if indegree[child] == 0:
					queue.append(child)
		return topo


from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		adj = [[] for i in range(K)]
		inDegree = [0 for i in range(K)]
		for i in range(N - 1):
			(w1, w2) = (alien_dict[i], alien_dict[i + 1])
			j = 0
			while j < len(w1) and j < len(w2):
				if w1[j] != w2[j]:
					(w1i, w2i) = (ord(w1[j]) - ord('a'), ord(w2[j]) - ord('a'))
					adj[w1i].append(w2i)
					inDegree[w2i] += 1
					break
				j += 1
		q = deque((i for i in range(K) if inDegree[i] == 0))
		ans = ''
		while q:
			node = q.popleft()
			ans += chr(node + ord('a'))
			for nxt in adj[node]:
				inDegree[nxt] -= 1
				if inDegree[nxt] == 0:
					q.append(nxt)
		return ans


import collections

class Solution:

	def findOrder(self, alien_dict, N, K):

		def topoSort(K, adj):
			topo = []
			V = K
			indegree = [0] * V
			for i in range(V):
				for ngb in adj[i]:
					indegree[ngb] += 1
			q = collections.deque()
			for i in range(V):
				if indegree[i] == 0:
					q.append(i)
			while q:
				node = q.popleft()
				topo.append(node)
				for v in adj[node]:
					indegree[v] -= 1
					if indegree[v] == 0:
						q.append(v)
			if len(topo) == V:
				return topo
		adj = [[] for i in range(K)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			mn = min(len(s1), len(s2))
			for j in range(mn):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		res = topoSort(K, adj)
		ans = ''
		for it in res:
			ans += chr(it + 97)
		return ans


class Solution:

	def findOrder(self, alien_dict, N, K):
		indegree = [0] * K
		stack = []
		queue = []
		adj = [[] for i in range(k)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			length = min(len(s1), len(s2))
			for j in range(length):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		for i in range(K):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(K):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop(0)
			stack.append(chr(ord('a') + x))
			for i in adj[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		return stack


class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			a = queue.pop(0)
			ans.append(a)
			for i in adj[a]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		if len(ans) == V:
			return ans
		else:
			return []

	def findOrder(self, alien_dict, N, K):
		adj = [[] for _ in range(K)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			a = min(len(s1), len(s2))
			for j in range(a):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		topo = self.topoSort(K, adj)
		ans = ''
		for l in topo:
			ans += chr(l + ord('a'))
		return ans


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		degree = defaultdict(int)
		for i in range(len(alien_dict) - 1):
			edges = self.comper(alien_dict[i], alien_dict[i + 1])
			if edges:
				graph[edges[0]].append(edges[1])
				degree[edges[0]] = 0 if edges[0] not in degree else degree[edges[0]]
				degree[edges[1]] += 1
		que = deque()
		for i in range(k):
			if not degree[chr(97 + i)]:
				que.append(chr(97 + i))
		order = []
		while que:
			curNode = que.popleft()
			order.append(curNode)
			for nbr in graph[curNode]:
				degree[nbr] -= 1
				if not degree[nbr]:
					que.append(nbr)
		return ''.join(order)

	def comper(self, str1, str2):
		i = j = 0
		while i < len(str1) and j < len(str2):
			if str1[i] != str2[j]:
				return (str1[i], str2[j])
			i += 1
			j += 1


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for i in range(len(alien_dict) - 1):
			edge = self.compareStrings(alien_dict[i], alien_dict[i + 1], indegree)
			if edge:
				graph[edge[0]].append(edge[1])
				indegree[edge[0]] = 0 if edge[0] not in indegree else indegree[edge[0]]
				indegree[edge[1]] += 1
		queue = deque()
		for i in range(k):
			if not indegree[chr(ord('a') + i)]:
				queue.append(chr(ord('a') + i))
		order = []
		while queue:
			letter = queue.popleft()
			order.append(letter)
			for neigh in graph[letter]:
				indegree[neigh] -= 1 if indegree[neigh] else 0
				if not indegree[neigh]:
					queue.append(neigh)
		return ''.join(order)

	def compareStrings(self, string1, string2, indegree):
		i = j = 0
		while i < len(string1) and j < len(string2):
			if string1[i] != string2[j]:
				return (string1[i], string2[j])
			i += 1
			j += 1


class Solution:

	def topoSort(self, v, adj):
		indegree = [0 for _ in range(v)]
		for i in range(0, v):
			for ele in adj[i]:
				indegree[ele] += 1
		q = []
		for i in range(v):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.pop(0)
			topo.append(node)
			for ele in adj[node]:
				indegree[ele] -= 1
				if indegree[ele] == 0:
					q.append(ele)
		return topo

	def findOrder(self, alien_dict, N, K):
		adj = [[] for _ in range(K)]
		for i in range(N - 1):
			S1 = alien_dict[i]
			S2 = alien_dict[i + 1]
			length = min(len(S1), len(S2))
			for ptr in range(length):
				if S1[ptr] != S2[ptr]:
					adj[ord(S1[ptr]) - ord('a')].append(ord(S2[ptr]) - ord('a'))
					break
		topo = self.topoSort(K, adj)
		ans = ''
		for elem in topo:
			ans = ans + chr(elem + ord('a'))
		return ans


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		incomings = defaultdict(int)
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			(p1, p2) = (0, 0)
			while p1 < len(word1) and p2 < len(word2) and (word1[p1] == word2[p2]):
				p1 += 1
				p2 += 1
			if p1 < len(word1) and p2 < len(word2):
				graph[word1[p1]].append(word2[p2])
				incomings[word2[p2]] += 1
		visited = set()
		queue = deque()
		answer = []
		for i in range(K):
			if incomings[chr(97 + i)] == 0:
				queue.append(chr(97 + i))
		while queue:
			curr = queue.popleft()
			answer.append(curr)
			for adj in graph[curr]:
				incomings[adj] -= 1
				if incomings[adj] == 0:
					queue.append(adj)
		return ''.join(answer)

	def dfs(self, graph, node, answer, visited):
		if len(graph[node]) == 0:
			answer.append(node)
			visited.add(node)
			return True
		visited.add(node)
		for next in graph[node]:
			if next not in visited:
				self.dfs(graph, next, answer, visited)
		answer.append(node)


class Solution:

	def findOrder(self, alien_dict, N, K):
		from collections import defaultdict, deque
		adjList = defaultdict(list)
		indegree = defaultdict(int)
		for i in range(N - 1):
			x = alien_dict[i]
			y = alien_dict[i + 1]
			length = min(len(x), len(y))
			for i in range(length):
				if x[i] != y[i]:
					adjList[x[i]].append(y[i])
					indegree[y[i]] += 1
					break
		queue = deque()
		ans = []
		for i in range(K):
			if indegree[chr(i + 97)] == 0:
				queue.append(chr(i + 97))
		while queue:
			curr = queue.popleft()
			ans.append(curr)
			for child in adjList[curr]:
				indegree[child] -= 1
				if indegree[child] == 0:
					queue.append(child)
		return ''.join(ans)


class Solution:

	def findOrder(self, alien_dict, N, K):
		alpha_num = {}
		num_alpha = {}
		for i in range(K):
			alpha_num[chr(i + 97)] = i
			num_alpha[i] = chr(i + 97)
		alien_dict = list(alien_dict)
		edges = []
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			min1 = min(len(word1), len(word2))
			ct = 0
			while ct < min1:
				if word1[ct] != word2[ct]:
					edges.append([alpha_num[word1[ct]], alpha_num[word2[ct]]])
					break
				ct += 1
		adj = {}
		for i in range(K):
			adj[i] = []
		for edge in edges:
			adj[edge[1]].append(edge[0])

		def dfs(node, adj, vis, stack):
			vis[node] = 1
			for adj_node in adj[node]:
				if vis[adj_node] == -1:
					dfs(adj_node, adj, vis, stack)
			stack.append(num_alpha[node])
		vis = [-1] * K
		stack = []
		for i in range(K):
			if vis[i] == -1:
				dfs(i, adj, vis, stack)
		return stack


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for curr in range(1, N):
			ltrPtr = 0
			prev = curr - 1
			max_size = min(len(alien_dict[prev]), len(alien_dict[curr]))
			while ltrPtr < max_size and alien_dict[prev][ltrPtr] == alien_dict[curr][ltrPtr]:
				ltrPtr += 1
			if ltrPtr < max_size:
				parent = alien_dict[prev][ltrPtr]
				child = alien_dict[curr][ltrPtr]
				graph[parent].append(child)
				indegree[child] += 1
		q = deque()
		for idx in range(k):
			letter = chr(97 + idx)
			if indegree[letter] == 0:
				q.append(letter)
		order = []
		while q:
			letter = q.popleft()
			order.append(letter)
			for child in graph[letter]:
				indegree[child] -= 1
				if indegree[child] == 0:
					q.append(child)
		return ''.join(order)


from collections import defaultdict
from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):

		def topoSort(V, adj):
			indegree = [0] * V
			for i in range(V):
				for n in adj[i]:
					indegree[n] += 1
			queue = []
			for i in range(V):
				if indegree[i] == 0:
					queue.append(i)
			cnt = 0
			top_order = []
			while queue:
				u = queue.pop(0)
				top_order.append(u)
				for i in adj[u]:
					indegree[i] -= 1
					if indegree[i] == 0:
						queue.append(i)
				cnt += 1
			if cnt == V:
				return top_order
			else:
				[]
		adj = defaultdict(list)
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			len_ = min(len(s1), len(s2))
			for ptr in range(len_):
				if s1[ptr] != s2[ptr]:
					adj[ord(s1[ptr]) - ord('a')].append(ord(s2[ptr]) - ord('a'))
					break
		topo = topoSort(K, adj)
		ans = ''
		for s in topo:
			ans += chr(s + ord('a'))
		return ans


from collections import defaultdict, deque

class Solution:

	def toposort(self, graph, k):
		in_degree = {v: 0 for v in range(k)}
		for v in graph:
			for neighbor in graph[v]:
				in_degree[neighbor] += 1
		queue = deque([v for v in in_degree if in_degree[v] == 0])
		result = []
		while queue:
			v = queue.popleft()
			result.append(v)
			for neighbor in graph[v]:
				in_degree[neighbor] -= 1
				if in_degree[neighbor] == 0:
					queue.append(neighbor)
		return result

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		for i in range(N - 1):
			m = min(len(alien_dict[i + 1]), len(alien_dict[i]))
			for j in range(m):
				if alien_dict[i][j] != alien_dict[i + 1][j]:
					graph[ord(alien_dict[i][j]) - ord('a')].append(ord(alien_dict[i + 1][j]) - ord('a'))
					break
		topo_sorted = self.toposort(graph, k)
		ans = ''
		for char in topo_sorted:
			ans += chr(char + ord('a'))
		return ans


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):

		def helper(arr):
			store = defaultdict(list)
			prev = arr[0][0]
			for item in arr:
				if len(item) > 1:
					store[item[0]].append(item[1:])
				if prev != item[0]:
					adj[prev].add(item[0])
					prev = item[0]
			for brr in store.values():
				if len(brr) > 1:
					helper(brr)

		def topology(node):
			if node in visited:
				return ''
			visited.add(node)
			temp = ''
			if node in adj:
				for item in adj[node]:
					temp = topology(item) + temp
			return node + temp
		adj = defaultdict(set)
		helper(alien_dict)
		output = ''
		visited = set()
		for node in adj:
			if not node in visited:
				output = topology(node) + output
		output += ''.join(set(''.join(alien_dict)) - set(output))
		return output


from collections import defaultdict
from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for index in range(N - 1):
			size = min(len(alien_dict[index]), len(alien_dict[index + 1]))
			for letter in range(size):
				if alien_dict[index][letter] != alien_dict[index + 1][letter]:
					graph[alien_dict[index][letter]].append(alien_dict[index + 1][letter])
					indegree[alien_dict[index + 1][letter]] += 1
					if alien_dict[index][letter] not in indegree:
						indegree[alien_dict[index][letter]] = 0
					break
		queue = deque()
		visted = set()
		for letter in indegree:
			if indegree[letter] == 0:
				queue.append(letter)
				visted.add(letter)
		answer = []
		while queue:
			node = queue.pop()
			answer.append(node)
			for child in graph[node]:
				indegree[child] -= 1
				if indegree[child] == 0:
					queue.append(child)
					visted.add(child)
		for ascii in range(ord('a'), ord('a') + K):
			letter = chr(ascii)
			if letter not in visted:
				answer.append(letter)
		return answer


import collections

class Solution:

	def findOrder(self, alien_dict, N, K):
		isedge = []
		for i in range(k):
			row = []
			for j in range(k):
				row.append(False)
			isedge.append(row)
		for i in range(len(alien_dict) - 1):
			(w1, w2) = (alien_dict[i], alien_dict[i + 1])
			minleng = min(len(w2), len(w1))
			for j in range(minleng):
				if w1[j] != w2[j]:
					isedge[ord(w1[j]) - 97][ord(w2[j]) - 97] = True
					break
		graph = collections.defaultdict(list)
		for i in range(k):
			for j in range(k):
				if isedge[i][j]:
					graph[i].append(j)
		res = []
		visted = [False] * k

		def dfs(i):
			visted[i] = True
			for adj in graph[i]:
				if not visted[adj]:
					dfs(adj)
			res.append(i)
		for i in range(k):
			if not visted[i]:
				dfs(i)
		ans = ''
		while res:
			i = res.pop()
			ans += chr(i + 97)
		return ans


from collections import *

class Solution:

	def findOrder(self, alien, N, K):
		graph = defaultdict(list)
		Indg = defaultdict(int)
		for i in range(N - 1):
			word1 = alien[i]
			word2 = alien[i + 1]
			for j in range(min(len(word1), len(word2))):
				if word1[j] != word2[j]:
					graph[word1[j]].append(word2[j])
					Indg[word2[j]] += 1
					break
		qu = deque()
		for i in range(k):
			if chr(97 + i) not in Indg:
				qu.append(chr(97 + i))
		ans = []
		while qu:
			node = qu.popleft()
			ans.append(node)
			for nbr in graph[node]:
				Indg[nbr] -= 1
				if Indg[nbr] == 0:
					qu.append(nbr)
		return ''.join(ans)


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		incoming = defaultdict(int)
		for i in range(n - 1):
			size = min(len(alien_dict[i]), len(alien_dict[i + 1]))
			for s in range(size):
				if alien_dict[i][s] != alien_dict[i + 1][s]:
					graph[alien_dict[i][s]].append(alien_dict[i + 1][s])
					incoming[alien_dict[i + 1][s]] += 1
					break
		visited = set()
		q = []
		ans = []

		def dfs(node, ans):
			if node in visited:
				return
			for neigh in graph[node]:
				dfs(neigh, ans)
			visited.add(node)
			ans.append(node)
			return
		for i in range(ord('a'), ord('a') + k):
			letter = chr(i)
			if incoming[letter] == 0:
				q.append(letter)
		for let in q:
			dfs(let, ans)
		ans.reverse()
		return ans


from collections import deque

class Solution:

	def findOrder(self, alien_dict, n, K):
		adj = [[] for i in range(K)]
		for i in range(n - 1):
			cur = alien_dict[i]
			nxt = alien_dict[i + 1]
			l = min(len(cur), len(nxt))
			for j in range(l):
				if cur[j] != nxt[j]:
					adj[ord(cur[j]) - ord('a')].append(ord(nxt[j]) - ord('a'))
					break

		def topoSort(V, adj):
			ans = []
			ind = [0] * V
			q = deque()
			for i in adj:
				for j in i:
					ind[j] = ind[j] + 1
			for i in range(V):
				if ind[i] == 0:
					q.appendleft(i)
			while q:
				p = q.pop()
				ans.append(p)
				for i in adj[p]:
					ind[i] = ind[i] - 1
					if ind[i] == 0:
						q.appendleft(i)
			return ans
		ans = topoSort(K, adj)
		a = []
		for el in ans:
			a.append(chr(el + ord('a')))
		return a


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):

		def dfs(node):
			if node in visited:
				return
			for neighbour in graph[node]:
				dfs(neighbour)
			alphabet_order_rev.append(node)
			visited.add(node)
			return
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for idx in range(N - 1):
			size = min(len(alien_dict[idx]), len(alien_dict[idx + 1]))
			for i in range(size):
				if alien_dict[idx][i] != alien_dict[idx + 1][i]:
					graph[alien_dict[idx][i]].append(alien_dict[idx + 1][i])
					indegree[alien_dict[idx + 1][i]] += 1
					break
		todo = []
		for ascii in range(ord('a'), ord('a') + k):
			letter = chr(ascii)
			if indegree[letter] == 0:
				todo.append(letter)
		alphabet_order_rev = []
		visited = set()
		for node in todo:
			dfs(node)
		return alphabet_order_rev[::-1]


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		dict = defaultdict(list)
		for i in range(len(alien_dict) - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			length = min(len(word1), len(word2))
			for w in range(length):
				if word1[w] == word2[w]:
					continue
				else:
					dict[ord(word1[w]) - 97].append(ord(word2[w]) - 97)
					break
		visited = [0 for i in range(K)]
		for ele in dict:
			for e in dict[ele]:
				visited[e] += 1
		queue = []
		res = []
		for (index, val) in enumerate(visited):
			if val == 0:
				queue.append(index)
		while len(queue) > 0:
			q = queue.pop(0)
			res.append(chr(q + 97))
			for ele in dict[q]:
				visited[ele] -= 1
				if visited[ele] == 0:
					queue.append(ele)
		return res


class Solution:

	def topoSort(self, adj, N):
		indegree = [0 for i in range(0, N)]
		queue = []
		topo = []
		for i in range(0, N):
			for v in adj[i]:
				indegree[v] += 1
		for i in range(0, N):
			if indegree[i] == 0:
				queue.append(i)
		while len(queue) != 0:
			node = queue.pop(0)
			topo.append(chr(node + 97))
			for v in adj[node]:
				indegree[v] -= 1
				if indegree[v] == 0:
					queue.append(v)
		return topo

	def findOrder(self, alien_dict, N, K):
		adj = [[] for i in range(0, K)]
		for i in range(0, N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			l = min(len(s1), len(s2))
			for i in range(0, l):
				if s1[i] != s2[i]:
					adj[ord(s1[i]) - 97].append(ord(s2[i]) - 97)
					break
		return self.topoSort(adj, K)


from collections import defaultdict, deque

class Solution:

	def getChild(self, word1, word2, store):
		length = min(len(word1), len(word2))
		for i in range(length):
			if word1[i] != word2[i]:
				store[word1[i]].add(word2[i])
				return

	def findOrder(self, alien_dict, N, K):
		store = defaultdict(set)
		for i in range(N - 1):
			self.getChild(alien_dict[i], alien_dict[i + 1], store)
		indeg = defaultdict(int)
		for i in range(K):
			indeg[chr(ord('a') + i)]
		for (key, values) in store.items():
			for val in values:
				indeg[val] += 1
		queue = deque()
		for (key, val) in indeg.items():
			if val == 0:
				queue.append(key)
		topSort = ''
		while queue:
			node = queue.popleft()
			topSort += node
			for val in store[node]:
				indeg[val] -= 1
				if indeg[val] == 0:
					queue.append(val)
		return topSort


from collections import defaultdict, Counter, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(set)
		incoming = Counter()
		queue = deque()
		order = []
		keys = set()
		for i in range(len(alien_dict) - 1):
			keys.update(alien_dict[i])
			keys.update(alien_dict[i + 1])
			if alien_dict[i][0] != alien_dict[i + 1][0]:
				if alien_dict[i + 1][0] not in graph[alien_dict[i][0]]:
					graph[alien_dict[i][0]].add(alien_dict[i + 1][0])
					incoming[alien_dict[i + 1][0]] += 1
			else:
				ptr = 1
				while ptr < len(alien_dict[i]) and ptr < len(alien_dict[i + 1]) and (alien_dict[i][ptr] == alien_dict[i + 1][ptr]):
					ptr += 1
				if ptr < len(alien_dict[i]) and ptr < len(alien_dict[i + 1]):
					if alien_dict[i + 1][ptr] not in graph[alien_dict[i][ptr]]:
						graph[alien_dict[i][ptr]].add(alien_dict[i + 1][ptr])
						incoming[alien_dict[i + 1][ptr]] += 1
		for k in list(keys):
			if incoming[k] == 0:
				queue.append(k)
		while queue:
			node = queue.popleft()
			order.append(node)
			for neighbor in graph[node]:
				incoming[neighbor] -= 1
				if incoming[neighbor] == 0:
					queue.append(neighbor)
		return order


class Solution:

	def solve(self, src, visited, topo, adj):
		visited.add(src)
		for i in adj[src]:
			if i not in visited:
				self.solve(i, visited, topo, adj)
		topo.append(src)

	def findOrder(self, alien_dict, N, K):
		adj = [[] for _ in range(K)]
		for i in range(1, N):
			s1 = alien_dict[i - 1]
			s2 = alien_dict[i]
			for j in range(min(len(s1), len(s2))):
				if s1[j] != s2[j]:
					u = ord(s1[j]) - ord('a')
					v = ord(s2[j]) - ord('a')
					adj[u].append(v)
					break
		visited = set()
		topo = []
		for i in range(K):
			if i not in visited:
				self.solve(i, visited, topo, adj)
		s = ''.join((chr(node + ord('a')) for node in topo[::-1]))
		return s


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		single = set()
		for i in range(N - 1):
			single.update(alien_dict[i])
			idx = 0
			while idx < len(alien_dict[i]) and idx < len(alien_dict[i + 1]) and (alien_dict[i][idx] == alien_dict[i + 1][idx]):
				idx += 1
			if idx < len(alien_dict[i]) and idx < len(alien_dict[i + 1]):
				graph[alien_dict[i][idx]].append(alien_dict[i + 1][idx])
		seen = set()
		res = []

		def dfs(letter):
			for child in graph[letter]:
				if child not in seen:
					dfs(child)
			res.append(letter)
			seen.add(letter)
		keys = list(graph.keys())
		for letter in keys:
			if letter not in seen:
				dfs(letter)
		res.reverse()
		for letter in single:
			if letter not in seen:
				res.append(letter)
		return ''.join(res)


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		answer = []
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for i in range(k):
			indegree[chr(97 + i)] = 0
		for r in range(N - 1):
			i = 0
			j = 0
			while i < len(alien_dict[r]) and j < len(alien_dict[r + 1]):
				if alien_dict[r][i] == alien_dict[r + 1][j]:
					i += 1
					j += 1
					continue
				else:
					graph[alien_dict[r][i]].append(alien_dict[r + 1][j])
					indegree[alien_dict[r + 1][j]] += 1
					break
		queue = deque()
		for (key, value) in indegree.items():
			if value == 0:
				queue.append(key)
		while queue:
			current = queue.popleft()
			answer.append(current)
			for neighbor in graph[current]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)
		return answer


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		outgoingSetMap = defaultdict(set)
		incomingCount = [0] * 26
		for word in alien_dict:
			for letter in word:
				outgoingSetMap[letter] = set()
		for i in range(len(alien_dict) - 1):
			curr_word = alien_dict[i]
			next_word = alien_dict[i + 1]
			counter = 0
			while counter < len(curr_word) and counter < len(next_word):
				curr_letter = curr_word[counter]
				next_letter = next_word[counter]
				if curr_letter != next_letter:
					if next_letter not in outgoingSetMap[curr_letter]:
						outgoingSetMap[curr_letter].add(next_letter)
						incomingCount[ord(next_letter) - ord('a')] += 1
					break
				else:
					counter += 1
		letter_order = []
		temp = []
		for letter in outgoingSetMap.keys():
			if incomingCount[ord(letter) - ord('a')] == 0:
				temp.append(letter)
		stage = deque(set(temp))
		while stage:
			current_letter = stage.popleft()
			letter_order.append(current_letter)
			for child in outgoingSetMap[current_letter]:
				incomingCount[ord(child) - ord('a')] -= 1
				if incomingCount[ord(child) - ord('a')] == 0:
					stage.append(child)
		return ''.join(letter_order)


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		incoming = defaultdict(int)
		queue = deque()
		sorted_order = []
		for index in range(len(alien_dict) - 1):
			min_val = min(len(alien_dict[index]), len(alien_dict[index + 1]))
			for i in range(min_val):
				if alien_dict[index][i] != alien_dict[index + 1][i]:
					graph[alien_dict[index][i]].append(alien_dict[index + 1][i])
					incoming[alien_dict[index + 1][i]] += 1
					break
		for i in range(K):
			if incoming[chr(i + 97)] == 0:
				queue.append(chr(i + 97))
		while queue:
			curr_letter = queue.popleft()
			sorted_order.append(curr_letter)
			for neighbor in graph[curr_letter]:
				incoming[neighbor] -= 1
				if incoming[neighbor] == 0:
					queue.append(neighbor)
		return ''.join(sorted_order)


from collections import defaultdict
from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		incoming = defaultdict(int)
		graph = defaultdict(list)
		queue = deque()
		for i in range(N - 1):
			other = self.setOrder(alien_dict[i], alien_dict[i + 1], graph)
			if other:
				incoming[other] += 1
		for i in range(K):
			if chr(97 + i) not in incoming:
				queue.append(chr(97 + i))
		result = ''
		while queue:
			letter = queue.popleft()
			result += letter
			for nbr in graph[letter]:
				incoming[nbr] -= 1
				if incoming[nbr] == 0:
					queue.append(nbr)
		return result

	def setOrder(self, word1, word2, graph):
		(size1, size2) = (len(word1), len(word2))
		for i in range(min(size2, size1)):
			if word1[i] != word2[i]:
				graph[word1[i]].append(word2[i])
				return word2[i]
		return None


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegre = defaultdict(int)
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			for j in range(min(len(s1), len(s2))):
				if s1[j] != s2[j]:
					graph[s1[j]].append(s2[j])
					indegre[s2[j]] += 1
					break
		que = deque()
		for i in range(K):
			if indegre[chr(i + 97)] == 0:
				que.append(chr(i + 97))
		res = []
		while que:
			node = que.popleft()
			res.append(node)
			for neighbor in graph[node]:
				indegre[neighbor] -= 1
				if indegre[neighbor] == 0:
					que.append(neighbor)
		return ''.join(res)


from collections import deque, defaultdict

class Solution:

	def findUnique(self, word1, word2):
		for i in range(len(word1)):
			if i < len(word2) and word1[i] != word2[i]:
				return (word1[i], word2[i])
		return ('', '')

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		Indegree = defaultdict(int)
		alien_dict = list(alien_dict)
		shift = 97
		source = set([chr(shift + i) for i in range(K)])
		for i in range(1, len(alien_dict)):
			(left, right) = self.findUnique(alien_dict[i - 1], alien_dict[i])
			if left:
				graph[right].append(left)
				Indegree[left] += 1
				if left in source:
					source.remove(left)
		answer = []
		queue = deque(list(source))
		visited = queue
		while queue:
			cur = queue.popleft()
			answer.append(cur)
			for child in graph[cur]:
				Indegree[child] -= 1
				if Indegree[child] == 0:
					queue.append(child)
		answer.reverse()
		return ''.join(answer)


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		incoming = defaultdict(int)
		alphabets = 'abcdefghijklmnopqrstuvwxyz'
		order = []
		for i in range(1, len(alien_dict)):
			for j in range(min(len(alien_dict[i - 1]), len(alien_dict[i]))):
				if alien_dict[i - 1][j] != alien_dict[i][j]:
					graph[alien_dict[i - 1][j]].append(alien_dict[i][j])
					incoming[alien_dict[i][j]] += 1
					break
		queue = deque()
		for i in range(K):
			if incoming[alphabets[i]] == 0:
				queue.append(alphabets[i])
		while queue:
			char = queue.popleft()
			order.append(char)
			for neighbour in graph[char]:
				incoming[neighbour] -= 1
				if incoming[neighbour] == 0:
					queue.append(neighbour)
		return order


from collections import *

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indeg = defaultdict(int)
		ord = []
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			for j in range(min(len(word1), len(word2))):
				if word1[j] != word2[j]:
					graph[word1[j]].append(word2[j])
					indeg[word2[j]] += 1
					break
		queue = deque()
		for i in range(k):
			if indeg[chr(i + 97)] == 0:
				queue.append(chr(i + 97))
		while queue:
			node = queue.popleft()
			ord.append(node)
			for neigh in graph[node]:
				indeg[neigh] -= 1
				if indeg[neigh] == 0:
					queue.append(neigh)
		return ''.join(ord)


from collections import defaultdict
import string

class Solution:

	def findOrder(self, alien_dict, N, K):
		adjList = defaultdict(set)
		ans = []
		for i in range(N):
			for j in range(i + 1, N):
				ptr1 = 0
				found = False
				while ptr1 < len(alien_dict[i]) and ptr1 < len(alien_dict[j]):
					if alien_dict[i][ptr1] != alien_dict[j][ptr1]:
						if alien_dict[i][ptr1] not in adjList[alien_dict[j][ptr1]]:
							adjList[alien_dict[j][ptr1]].add(alien_dict[i][ptr1])
						found = True
						break
					ptr1 += 1
				if found:
					break

		def dfs(node, visited=set()):
			if node in visited:
				return
			visited.add(node)
			for child in adjList[node]:
				dfs(child, visited)
			ans.append(node)
		for letter in string.ascii_lowercase[:K]:
			dfs(letter)
		return ans


from collections import deque, defaultdict

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for vertice in adj[node]:
				indegree[vertice] += 1
		q = deque()
		for node in range(V):
			if indegree[node] == 0:
				q.append(node)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for vertice in adj[node]:
				indegree[vertice] -= 1
				if indegree[vertice] == 0:
					q.append(vertice)
		return ans if len(ans) == V else []

	def findOrder(self, alien_dict, N, K):
		adj = defaultdict(list)
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			l = min(len(s1), len(s2))
			for j in range(l):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		ans = self.topoSort(K, adj)
		return ''.join((chr(i + ord('a')) for i in ans))


class Solution:

	def findOrder(self, alien_dict, N, K):
		adj = {chr(97 + i): set() for i in range(K)}
		for i in range(N - 1):
			(word_one, word_two) = (alien_dict[i], alien_dict[i + 1])
			length = min(len(word_one), len(word_two))
			for j in range(length):
				if word_one[j] != word_two[j]:
					adj[word_one[j]].add(word_two[j])
					break
		visited = {}
		res = []

		def dfs(char):
			if char in visited:
				return visited[char]
			visited[char] = True
			for neighChar in adj[char]:
				if dfs(neighChar):
					return True
			visited[char] = False
			res.append(char)
		for char in adj:
			if dfs(char):
				return []
		res.reverse()
		return res


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		indegree = defaultdict(int)
		graph = defaultdict(set)
		order = []
		for word in alien_dict:
			for lett in word:
				indegree[lett] = 0
		prev = alien_dict[0]
		for current in alien_dict[1:]:
			for (a, b) in zip(prev, current):
				if a != b:
					if b not in graph[a]:
						graph[a].add(b)
						indegree[b] += 1
					break
			prev = current
		Q = deque()
		for (key, value) in indegree.items():
			if value == 0:
				Q.append(key)
		while Q:
			current = Q.popleft()
			order.append(current)
			for adj in graph[current]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					Q.append(adj)
		return ''.join(order)


class Solution:

	def findOrder(self, alien_dict, N, K):
		adj = {char: set() for word in alien_dict for char in word}
		for i in range(len(alien_dict) - 1):
			(word_one, w2) = (alien_dict[i], alien_dict[i + 1])
			minLen = min(len(word_one), len(w2))
			for j in range(minLen):
				if word_one[j] != w2[j]:
					adj[word_one[j]].add(w2[j])
					break
		visited = {}
		res = []

		def dfs(char):
			if char in visited:
				return visited[char]
			visited[char] = True
			for neighChar in adj[char]:
				if dfs(neighChar):
					return True
			visited[char] = False
			res.append(char)
		for char in adj:
			if dfs(char):
				return []
		res.reverse()
		return res


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indeg = defaultdict(int)
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			for j in range(min(len(word1), len(word2))):
				if word1[j] != word2[j]:
					graph[word1[j]].append(word2[j])
					indeg[word2[j]] += 1
					break
			stack = []
			res = []
		for i in range(K):
			if indeg[chr(i + 97)] == 0:
				stack.append(chr(i + 97))
		while stack:
			cur = stack.pop()
			res.append(cur)
			for nbr in graph[cur]:
				indeg[nbr] -= 1
				if indeg[nbr] == 0:
					stack.append(nbr)
		return res


from collections import defaultdict, deque

class Solution:

	def __init__(self):
		self.inc = defaultdict(int)
		self.alphabet = set()

	def createGraph(self, alien_dict):
		graph = defaultdict(list)
		pointer_stack = []
		i = 0
		while i < len(alien_dict) - 1:
			j = 0
			while j < min(len(alien_dict[i]), len(alien_dict[i + 1])) and alien_dict[i][j] == alien_dict[i + 1][j]:
				j += 1
			if j < min(len(alien_dict[i]), len(alien_dict[i + 1])):
				graph[alien_dict[i][j]].append(alien_dict[i + 1][j])
				self.inc[alien_dict[i + 1][j]] += 1
			self.alphabet = self.alphabet | set(alien_dict[i])
			i += 1
		self.alphabet = self.alphabet | set(alien_dict[i])
		return graph

	def findOrder(self, alien_dict, N, K):
		graph = self.createGraph(alien_dict)
		q = deque([i for i in self.alphabet if self.inc[i] == 0])
		order = []
		while q:
			x = q.popleft()
			order.append(x)
			for nbr in graph[x]:
				self.inc[nbr] -= 1
				if self.inc[nbr] == 0:
					q.append(nbr)
		return order


from collections import *

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indeg = defaultdict(int)
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			for i in range(min(len(word1), len(word2))):
				if word1[i] != word2[i]:
					graph[word1[i]].append(word2[i])
					indeg[word2[i]] += 1
					break
		stack = []
		res = []
		for i in range(k):
			if indeg[chr(i + 97)] == 0:
				stack.append(chr(i + 97))
		while stack:
			temp = stack.pop()
			res.append(temp)
			for elm in graph[temp]:
				indeg[elm] -= 1
				if indeg[elm] == 0:
					stack.append(elm)
		return ''.join(res)


import collections

class Solution:

	def findOrder(self, alien_dict, n, k):
		graph = collections.defaultdict(list)
		start = {}
		que = set()
		for word in alien_dict:
			for char in word:
				start[char] = 0
				que.add(char)
		for i in range(n - 1):
			(word, nuxt) = (alien_dict[i], alien_dict[i + 1])
			index = 0
			while index < len(word) and word[index] == nuxt[index]:
				index += 1
			if index < len(word):
				graph[word[index]].append(nuxt[index])
				start[nuxt[index]] += 1
				que.discard(nuxt[index])
		que = collections.deque(que)
		alphabet = ''
		while que:
			char = que.popleft()
			alphabet += char
			for child in graph[char]:
				start[child] -= 1
				if start[child] == 0:
					que.append(child)
		return alphabet


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		dic = defaultdict(list)
		incoming = defaultdict(int)
		chars = set([chr(i + 97) for i in range(k)])
		for i in range(1, n):
			for j in range(len(alien_dict[i - 1])):
				if alien_dict[i - 1][j] != alien_dict[i][j]:
					dic[alien_dict[i - 1][j]].append(alien_dict[i][j])
					incoming[alien_dict[i][j]] += 1
					break
		queue = deque()
		for i in chars:
			if incoming[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			x = queue.popleft()
			ans.append(x)
			for i in dic[x]:
				incoming[i] -= 1
				if incoming[i] == 0:
					queue.append(i)
		return ''.join(ans)


import collections

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = collections.defaultdict(list)
		start = {}
		for i in range(n):
			for char in alien_dict[i]:
				start[char] = 0
		for i in range(N - 1):
			(word, nuxt) = (alien_dict[i], alien_dict[i + 1])
			char = 0
			while char < len(word) and word[char] == nuxt[char]:
				char += 1
			if char < len(word):
				graph[word[char]].append(nuxt[char])
				start[word[char]] += 0
				start[nuxt[char]] += 1
		que = collections.deque([])
		alphabet = ''
		for char in start:
			if start[char] == 0:
				que.append(char)
				alphabet += char
		while que:
			char = que.popleft()
			for child in graph[char]:
				start[child] -= 1
				if start[child] == 0:
					que.append(child)
					alphabet += child
		for char in start:
			if char not in alphabet:
				alphabet += char
		return alphabet


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		queue = deque([])
		all_letter = set()
		char_order = []
		for word in range(len(alien_dict) - 1):
			cur_word = alien_dict[word]
			next_word = alien_dict[word + 1]
			min_len = min(len(cur_word), len(next_word))
			for ptr in range(min_len):
				if cur_word[ptr] == next_word[ptr]:
					continue
				graph[cur_word[ptr]].append(next_word[ptr])
				indegree[next_word[ptr]] += 1
				break
		for word in alien_dict:
			for char in word:
				all_letter.add(char)
		for character in all_letter:
			if indegree[character] == 0:
				queue.append(character)
		while queue:
			cur_char = queue.popleft()
			char_order.append(cur_char)
			for next_char in graph[cur_char]:
				indegree[next_char] -= 1
				if indegree[next_char] == 0:
					queue.append(next_char)
		return ''.join(char_order)


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		letter_collections = set(list(alien_dict[0]))
		for i in range(1, len(alien_dict)):
			ptr = 0
			(word1, word2) = (alien_dict[i - 1], alien_dict[i])
			letter_collections = letter_collections.union(list(word2))
			while ptr < min(len(word1), len(word2)):
				if word1[ptr] != word2[ptr]:
					graph[word2[ptr]].append(word1[ptr])
					break
				ptr += 1
		color = defaultdict(int)

		def dfs(node):
			if color[node] == 2:
				return True
			if all([dfs(neighnor) for neighnor in graph[node]]):
				color[node] = 2
				ans.append(node)
				return True
		ans = []
		for letter in letter_collections:
			dfs(letter)
		return ''.join(ans)


from collections import defaultdict

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		color = defaultdict(int)
		ans = []
		alphabet = set(list(alien_dict[0]))
		for i in range(len(alien_dict) - 1):
			alphabet = alphabet.union(set(list(alien_dict[i + 1])))
			for j in range(min(len(alien_dict[i]), len(alien_dict[i + 1]))):
				if alien_dict[i][j] == alien_dict[i + 1][j]:
					continue
				graph[alien_dict[i + 1][j]].append(alien_dict[i][j])
				break

		def dfs(node):
			if color[node] == 2:
				return True
			elif color[node] == 0:
				color[node] = 1
				if all([dfs(nbr) for nbr in graph[node]]):
					ans.append(node)
					color[node] = 2
					return True
			return False
		for letter in alphabet:
			if color[letter] == 0:
				dfs(letter)
		return ''.join(ans)


from collections import defaultdict
from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indgree = defaultdict(int)
		for i in range(N):
			for ch in alien_dict[i]:
				indgree[ch] = 0
		for i in range(N - 1):
			a = alien_dict[i]
			b = alien_dict[i + 1]
			ptr = 0
			for j in range(min(len(a), len(b))):
				if a[j] == b[j]:
					continue
				graph[a[j]].append(b[j])
				indgree[b[j]] += 1
				break
		q = deque([key for key in indgree if indgree[key] == 0])
		order = []
		while q:
			ch = q.popleft()
			order.append(ch)
			for let in graph[ch]:
				indgree[let] -= 1
				if indgree[let] == 0:
					q.append(let)
		return order


from collections import defaultdict
from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for i in range(k):
			indegree[chr(97 + i)] = 0
		for i in range(N - 1):
			word1 = alien_dict[i]
			word2 = alien_dict[i + 1]
			p1 = p2 = 0
			while p1 < len(word1) and p2 < len(word2):
				if word1[p1] == word2[p2]:
					p1 += 1
					p2 += 1
					continue
				else:
					graph[word1[p1]].append(word2[p2])
					indegree[word2[p2]] += 1
					break
		queue = deque([])
		for key in indegree:
			if indegree[key] == 0:
				queue.append(key)
		order = []
		while queue:
			value = queue.popleft()
			order.append(value)
			for child in graph[value]:
				indegree[child] -= 1
				if indegree[child] == 0:
					queue.append(child)
		return order


class Solution:

	def findOrder(self, alien_dict, N, K):
		code = [[0, i] for i in range(k)]

		def string(a, b):
			n = min(len(a), len(b))
			for i in range(n):
				if a[i] != b[i]:
					code[ord(a[i]) - ord('a')][0] = code[ord(a[i]) - ord('a')][0] | 1 << ord(b[i]) - ord('a') | code[ord(b[i]) - ord('a')][0]
					return
		for i in range(N - 1, 0, -1):
			string(alien_dict[i - 1], alien_dict[i])
		for i in range(N - 1, 0, -1):
			string(alien_dict[i - 1], alien_dict[i])
		code.sort(key=lambda x: bin(x[0]).count('1'))
		ans = ''
		for (a, b) in code:
			ans = chr(b + ord('a')) + ans
		return ans


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		adjList = defaultdict(list)
		characters = set()
		indegree = defaultdict(int)
		for index in range(len(alien_dict) - 1):
			word1 = alien_dict[index]
			word2 = alien_dict[index + 1]
			limit = min(len(word1), len(word2))
			for ptr in range(limit):
				if word1[ptr] == word2[ptr]:
					continue
				adjList[word1[ptr]].append(word2[ptr])
				indegree[word2[ptr]] += 1
				break
		for word in alien_dict:
			for character in word:
				characters.add(character)
		queue = deque()
		for character in characters:
			if indegree[character] == 0:
				queue.append(character)
		order = []
		while queue:
			curr = queue.pop()
			order.append(curr)
			for neighbor in adjList[curr]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)
		return ''.join(order)


from collections import defaultdict, deque

class Solution:

	def topoSort(self, n: int, adj: defaultdict):
		indegree = defaultdict(int)
		for i in range(n):
			for node in adj[i]:
				indegree[node] += 1
		queue = deque()
		for node in range(n):
			if indegree[node] == 0:
				queue.append(node)
		answer = []
		while queue:
			temp = queue.popleft()
			answer.append(temp)
			for neighbour in adj[temp]:
				indegree[neighbour] -= 1
				if indegree[neighbour] == 0:
					queue.append(neighbour)
		return answer

	def findOrder(self, alien_dict, N, K):
		adjList = defaultdict(list)
		for i in range(N - 1):
			(s1, s2) = (alien_dict[i], alien_dict[i + 1])
			length = min(len(s1), len(s2))
			for j in range(length):
				if s1[j] != s2[j]:
					adjList[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		topo = self.topoSort(K, adjList)
		ans = ''
		for node in topo:
			ans += chr(node + ord('a'))
		return ans


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(set)
		count = defaultdict(int)
		for i in range(1, len(alien_dict)):
			prev = alien_dict[i - 1]
			curr = alien_dict[i]
			for j in range(min(len(prev), len(curr))):
				if prev[j] != curr[j]:
					if curr[j] not in graph[prev[j]]:
						graph[prev[j]].add(curr[j])
						count[curr[j]] += 1
					break
		queue = deque()
		for i in range(K):
			letter = chr(97 + i)
			if count[letter] == 0:
				queue.append(letter)
		result = []
		while queue:
			curr = queue.popleft()
			result.append(curr)
			for neigh in graph[curr]:
				count[neigh] -= 1
				if count[neigh] == 0:
					queue.append(neigh)
		return result


from collections import defaultdict

class Solution:

	def findOrder(self, words, N, K):
		adj_list = defaultdict(set)
		in_degree = {char: 0 for word in words for char in word}
		for i in range(N - 1):
			(word1, word2) = (words[i], words[i + 1])
			for j in range(min(len(word1), len(word2))):
				if word1[j] != word2[j]:
					if word2[j] not in adj_list[word1[j]]:
						adj_list[word1[j]].add(word2[j])
						in_degree[word2[j]] += 1
					break
			else:
				if len(word1) > len(word2):
					return ''
		ans = []
		queue = [char for char in in_degree if in_degree[char] == 0]
		colors = {char: 0 for word in words for char in word}

		def dfs(cur):
			if colors[cur] == 2:
				return False
			if colors[cur] == 1:
				return True
			colors[cur] = 1
			for nei in adj_list[cur]:
				hascycle = dfs(nei)
				if hascycle:
					return True
			colors[cur] = 2
			ans.append(cur)
		for n in queue:
			cycle = dfs(n)
			if cycle:
				return ''
		order = []
		order = ans
		queue = []
		while queue:
			char = queue.pop(0)
			order.append(char)
			for nei in adj_list[char]:
				in_degree[nei] -= 1
				if in_degree[nei] == 0:
					queue.append(nei)
		if len(order) == len(in_degree):
			order = reversed(order)
			return ''.join(order)
		else:
			return ''


from collections import defaultdict

class Solution:

	def findOrder(self, words, N, K):
		adj_list = defaultdict(set)
		in_degree = {char: 0 for word in words for char in word}
		for i in range(N - 1):
			(word1, word2) = (words[i], words[i + 1])
			for j in range(min(len(word1), len(word2))):
				if word1[j] != word2[j]:
					if word2[j] not in adj_list[word1[j]]:
						adj_list[word1[j]].add(word2[j])
						in_degree[word2[j]] += 1
					break
			else:
				if len(word1) > len(word2):
					return ''
		queue = [char for char in in_degree if in_degree[char] == 0]
		order = []
		while queue:
			char = queue.pop(0)
			order.append(char)
			for nei in adj_list[char]:
				in_degree[nei] -= 1
				if in_degree[nei] == 0:
					queue.append(nei)
		if len(order) == len(in_degree):
			return ''.join(order)
		else:
			return ''


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		in_coming = defaultdict(int)
		order = []
		starting_alphabets = []
		n = len(alien_dict)
		queue = deque()
		for i in range(n - 1):
			for (char1, char2) in zip(alien_dict[i], alien_dict[i + 1]):
				if char1 == char2:
					continue
				graph[char1].append(char2)
				in_coming[char2] += 1
				break
			starting_alphabets.append(alien_dict[i])
		starting_alphabets.append(alien_dict[n - 1])
		starting_alphabets = set(list(''.join(starting_alphabets)))
		for chars in starting_alphabets:
			if in_coming[chars] == 0:
				queue.append(chars)

		def bfs(queue):
			while queue:
				char = queue.popleft()
				order.append(char)
				for neighbour in graph[char]:
					in_coming[neighbour] -= 1
					if in_coming[neighbour] == 0:
						queue.append(neighbour)
			return order
		return bfs(queue)


class graph:

	def __init__(self, k):
		self.matrix = [[False for _ in range(k)] for _ in range(k)]
		self.ancestors = [0 for _ in range(k)]
		self.index = {}
		self.next_index = 0
		self.characters = ''

	def add_char(self, char):
		if char in self.index:
			return
		self.index[char] = self.next_index
		self.next_index += 1
		self.characters += char

	def add_edge(self, first, second):
		i1 = self.index[first]
		i2 = self.index[second]
		if self.matrix[i1][i2]:
			return
		self.ancestors[i2] += 1
		self.matrix[i1][i2] = True

	def dfs(self, location, order):
		if self.ancestors[location] > 1:
			self.ancestors[location] -= 1
			return
		order.append(self.characters[location])
		for i in range(len(self.matrix)):
			if self.matrix[location][i]:
				self.dfs(i, order)

	def topo_sort(self):
		order = []
		for i in range(len(self.matrix)):
			if self.ancestors[i] == 0:
				self.dfs(i, order)
		return order

class Solution:

	def findOrder(self, alien_dict, n, k):
		g = graph(k)
		for c in alien_dict[0]:
			g.add_char(c)
		for i in range(1, n):
			for c in alien_dict[i]:
				g.add_char(c)
			length = min(len(alien_dict[i]), len(alien_dict[i - 1]))
			for j in range(length):
				if alien_dict[i - 1][j] != alien_dict[i][j]:
					g.add_edge(alien_dict[i - 1][j], alien_dict[i][j])
					break
		lst = g.topo_sort()
		order = ''
		for c in lst:
			order += c
		return order


class Solution:

	def findOrder(self, alien_dict, N, M):
		adj = [set() for _ in range(M)]
		status = [0 for _ in range(M)]
		S = max([0 for _ in range(N)], key=lambda x: len(alien_dict[x]))
		match = alien_dict[0][0]
		for i in range(len(alien_dict[S])):
			for j in range(N):
				curr = alien_dict[j][:i + 1]
				if curr != match:
					if curr[:-1] == match[:-1]:
						adj[ord(match[-1]) - ord('a')].add(ord(curr[-1]) - ord('a'))
					match = curr
		ans = []

		def dfs(node):
			if status[node]:
				return status[node] == 1
			status[node] = 1
			for neigh in adj[node]:
				if dfs(neigh):
					return True
			status[node] = 2
			ans.append(chr(node + ord('a')))
			return False
		for i in range(M):
			if not status[i] and dfs(i):
				return ''
		ans = ans[::-1]
		ans = ''.join(ans)
		return ans


from typing import List
from collections import deque

class Solution:

	def findOrder(self, alien_dict: List[str], N: int, K: int) -> int:
		graph = [[] for _ in range(K)]
		indegree = [0 for _ in range(K)]
		for idx in range(1, len(alien_dict)):
			j = 0
			(prev, curr) = (alien_dict[idx - 1], alien_dict[idx])
			while j < min(len(prev), len(curr)):
				if prev[j] != curr[j]:
					graph[ord(prev[j]) - 97].append(ord(curr[j]) - 97)
					indegree[ord(curr[j]) - 97] += 1
					break
				j += 1
		queue = deque()
		for (idx, elem) in enumerate(indegree):
			if elem == 0:
				queue.append(idx)
		order = []
		while queue:
			val = queue.popleft()
			order.append(chr(val + 97))
			for neighbour in graph[val]:
				indegree[neighbour] -= 1
				if indegree[neighbour] == 0:
					queue.append(neighbour)
		return order


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		order = []
		graph = defaultdict(list)
		for i in range(N - 1):
			curr = alien_dict[i]
			nxt = alien_dict[i + 1]
			for j in range(min(len(curr), len(nxt))):
				if curr[j] != nxt[j]:
					graph[ord(curr[j]) - ord('a')].append(ord(nxt[j]) - ord('a'))
					break
		incoming = defaultdict(int)
		queue = deque()
		for node in graph:
			for neigh in graph[node]:
				incoming[neigh] += 1
		for node in range(k):
			if incoming[node] == 0:
				queue.append(node)
		while queue:
			curr = queue.popleft()
			order.append(curr)
			for neighbor in graph[curr]:
				incoming[neighbor] -= 1
				if incoming[neighbor] == 0:
					queue.append(neighbor)
		for (i, num) in enumerate(order):
			order[i] = chr(num + ord('a'))
		return order


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		d = defaultdict(list)
		order = alien_dict
		(l, r) = (0, 1)
		while r < len(order):
			i = 0
			while i < len(order[l]) and i < len(order[r]):
				if order[l][i] != order[r][i]:
					d[order[l][i]].append(order[r][i])
					break
				i += 1
			l += 1
			r += 1
		characters = set()
		for word in order:
			for char in word:
				characters.add(char)
		characters = list(characters)
		indegree = defaultdict(int)
		for key in d:
			for after in d[key]:
				indegree[after] += 1
		todo = deque()
		for key in characters:
			if indegree[key] == 0:
				todo.appendleft(key)
		res = []
		while todo:
			curr = todo.pop()
			res.append(curr)
			for after in d[curr]:
				indegree[after] -= 1
				if indegree[after] == 0:
					todo.appendleft(after)
		return ''.join(res)


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		indegree = defaultdict(int)
		all_chars = set(alien_dict[0])
		for i in range(1, len(alien_dict)):
			all_chars.update(alien_dict[i])
			for (a, b) in zip(alien_dict[i - 1], alien_dict[i]):
				if a != b:
					graph[a].append(b)
					indegree[b] += 1
					break
		queue = deque()
		for char in all_chars:
			if indegree[char] == 0:
				queue.append(char)
		order = []
		while queue:
			current = queue.popleft()
			order.append(current)
			for nbr in graph[current]:
				indegree[nbr] -= 1
				if indegree[nbr] == 0:
					queue.append(nbr)
		return order


from collections import deque

class Solution:

	def findOrder(self, alienDic, N, K):
		graph = {}
		size = len(alienDic)
		nonStarters = set()
		allChars = set()
		for word in alienDic:
			for ch in word:
				allChars.add(ch)
		for idx in range(size - 1):
			res = self.processWords(alienDic[idx], alienDic[idx + 1])
			if res:
				(pre, after) = res
				nonStarters.add(after)
				if pre in graph:
					graph[pre].append(after)
				else:
					graph[pre] = [after]
		starters = []
		for key in graph.keys():
			if key not in nonStarters:
				starters.append(key)
		result = self.topologicalSort(graph, starters)
		allChars = list(allChars)
		setResult = set(result)
		for ch in allChars:
			if ch not in setResult:
				result.append(ch)
		return result

	def processWords(self, word1, word2):
		p1 = 0
		p2 = 0
		n = len(word1)
		m = len(word2)
		while p1 < n and p2 < m and (word1[p1] == word2[p2]):
			p1 += 1
			p2 += 1
		if p1 < n and p2 < m and (word1[p1] != word2[p2]):
			return (word1[p1], word2[p2])
		return False

	def topologicalSort(self, graph, starters):
		for key in graph.keys():
			graph[key] = list(set(graph[key]))
		q = deque(starters)
		visited = set()
		stack = []
		preReqs = {}
		for pre in graph.keys():
			for node in graph[pre]:
				if node in preReqs:
					preReqs[node] += 1
				else:
					preReqs[node] = 1
		while q:
			node = q.popleft()
			stack.append(node)
			if node in graph:
				for neig in graph[node]:
					preReqs[neig] -= 1
					if neig not in visited and preReqs[neig] == 0:
						visited.add(neig)
						q.append(neig)
		return stack


from collections import defaultdict, deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		GRAPH = defaultdict(list)
		for i in range(1, N):
			(str1, str2) = (alien_dict[i - 1], alien_dict[i])
			ans = self.fd_chars(str1, str2)
			if ans:
				GRAPH[ans[0]].append(ans[1])
		return self.top_sort(GRAPH, K)

	def fd_chars(self, str1, str2):
		for (char1, char2) in zip(str1, str2):
			if char1 != char2:
				return (char1, char2)
		return []

	def top_sort(self, graph, k):
		(INDEGREE, queue) = (defaultdict(int), deque())
		order = []
		for children in graph.values():
			for node in children:
				INDEGREE[node] += 1
		for i in range(k):
			curr_node = chr(97 + i)
			if not INDEGREE[curr_node]:
				queue.append(curr_node)
		while queue:
			node = queue.popleft()
			order.append(node)
			for adj in graph[node]:
				if INDEGREE[adj]:
					INDEGREE[adj] -= 1
					if not INDEGREE[adj]:
						queue.append(adj)
		return ''.join(order)


from queue import Queue

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		q = Queue()
		for node in range(V):
			if indegree[node] == 0:
				q.put(node)
		topo = []
		while not q.empty():
			node = q.get()
			topo.append(node)
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					q.put(adjNode)
		return topo

	def findOrder(self, alien_dict, N, K):
		adj = [[] for i in range(K)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			minLen = min(len(s1), len(s2))
			for j in range(minLen):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		topo = Solution.topoSort(self, K, adj)
		ans = ''
		for it in topo:
			ans += chr(it + ord('a'))
		return ans


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		(topo, indegrees) = ([], [0] * V)
		for adjNodes in adj:
			for adjNode in adjNodes:
				indegrees[adjNode] += 1
		que = deque()
		for node in range(V):
			if indegrees[node] == 0:
				que.append(node)
		while que:
			node = que.popleft()
			topo.append(node)
			for adjNode in adj[node]:
				indegrees[adjNode] -= 1
				if indegrees[adjNode] == 0:
					que.append(adjNode)
		return topo

	def findOrder(self, alien_dict, N, K):
		adj = [[] for i in range(K)]
		for i in range(N - 1):
			j = 0
			first = alien_dict[i]
			second = alien_dict[i + 1]
			while j < len(first) and j < len(second):
				if first[j] != second[j]:
					adj[ord(first[j]) - 97].append(ord(second[j]) - 97)
					break
				j += 1
		topo = self.topoSort(K, adj)
		res = []
		for item in topo:
			res.append(chr(item + 97))
		return res


import collections

class Solution:

	def topoSort(self, characters, adj):
		indegree = collections.defaultdict(int)
		for k in adj:
			for v in adj[k]:
				indegree[v] += 1
		q = []
		for k in characters:
			if indegree[k] == 0:
				q.append(k)
		res = []
		while q:
			c = q.pop()
			res.append(c)
			for v in adj[c]:
				indegree[v] -= 1
				if indegree[v] == 0:
					q.append(v)
		return res if len(res) == len(characters) else []

	def findOrder(self, alien_dict, N, K):
		adj = collections.defaultdict(list)
		s = ''
		for k in alien_dict:
			s += k
		characters = list(set(s))
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			for j in range(min(len(s1), len(s2))):
				if s1[j] != s2[j]:
					adj[s1[j]].append(s2[j])
					break
		return ''.join(self.topoSort(characters, adj))


class Solution:

	def tropo_sort(self, adj, k):
		indegree = [0] * k
		for i in adj:
			for j in i:
				indegree[j] += 1
		temp = []
		for i in range(k):
			if indegree[i] == 0:
				temp.append(i)
		result = []
		while temp:
			x = temp.pop(0)
			y = adj[x].copy()
			while y:
				l = y.pop(0)
				indegree[l] -= 1
				if indegree[l] == 0:
					temp.append(l)
			result.append(chr(x + ord('a')))
		return result

	def findOrder(self, alien_dict, N, K):
		adj = []
		for i in range(k):
			adj.append([])
		for i in range(len(alien_dict) - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			for j in range(min(len(s1), len(s2))):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		return self.tropo_sort(adj, k)


import string
from queue import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		d = {}
		alphabet = list(string.ascii_lowercase)
		for i in alphabet:
			d[i] = ord(i) - 97
		adj = [[] for i in range(K)]
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			n = min(len(s1), len(s2))
			for i in range(n):
				if s1[i] == s2[i]:
					continue
				else:
					adj[d[s1[i]]].append(d[s2[i]])
					break
		indeg = {}
		for i in range(K):
			indeg[i] = 0
		for i in range(len(adj)):
			for j in adj[i]:
				indeg[j] += 1
		q = deque()
		for i in indeg:
			if indeg[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for nbr in adj[node]:
				indeg[nbr] -= 1
				if indeg[nbr] == 0:
					q.append(nbr)
		d = {}
		for i in range(26):
			d[i] = chr(97 + i)
		for i in range(len(ans)):
			ans[i] = d[ans[i]]
		return ans


from queue import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		adj = [[] for i in range(K)]
		for i in range(len(alien_dict) - 1):
			str1 = alien_dict[i]
			str2 = alien_dict[i + 1]
			(j1, j2) = (0, 0)
			while j1 < len(str1) and j2 < len(str2):
				if str1[j1] != str2[j2]:
					adj[ord(str1[j1]) - 97].append(ord(str2[j2]) - 97)
					break
				else:
					j1 += 1
					j2 += 1
		indegree = {}
		q = deque()
		for i in range(len(adj)):
			indegree[i] = 0
		for i in adj:
			for j in i:
				indegree[j] = indegree[j] + 1
		for i in indegree:
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(chr(node + 97))
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return ans


import collections

class Solution:

	def findOrder(self, alien_dict, N, K):

		def compareWords(word1, word2):
			if word1 == word2:
				return (None, None)
			(N1, N2) = (len(word1), len(word2))
			(i, j) = (0, 0)
			while i < N1 and j < N2:
				if word1[i] == word2[j]:
					i += 1
					j += 1
					continue
				return (word1[i], word2[j])
			return (None, None)
		adj = collections.defaultdict(set)
		for i in range(1, N):
			(u, v) = compareWords(alien_dict[i - 1], alien_dict[i])
			if u and v:
				adj[ord(u) - ord('a')].add(ord(v) - ord('a'))
		incEdges = [0] * K
		for u in adj:
			for v in adj[u]:
				incEdges[v] += 1
		q = collections.deque([])
		for (letter, count) in enumerate(incEdges):
			if count == 0:
				q.append(letter)
		ans = []
		while q:
			curr = q.popleft()
			ans.append(chr(curr + ord('a')))
			for v in adj[curr]:
				incEdges[v] -= 1
				if incEdges[v] == 0:
					q.append(v)
		return ans


class Solution:

	def findOrder(self, alien_dict, N, K):
		from collections import deque
		q = deque()
		ans = []
		adj = {}
		indegree = {}
		for i in range(97, 97 + K):
			adj[chr(i)] = []
			indegree[chr(i)] = 0
		for i in range(1, N):
			s1 = alien_dict[i - 1]
			s2 = alien_dict[i]
			(p1, p2) = (0, 0)
			while p1 < len(s1) and p2 < len(s2):
				if s1[p1] != s2[p2]:
					adj[s1[p1]].append(s2[p2])
					indegree[s2[p2]] += 1
					break
				p1 += 1
				p2 += 1
		for i in adj:
			if indegree[i] == 0:
				q.append(i)
		while len(q) > 0:
			val = q.popleft()
			ans.append(val)
			for i in adj[val]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return ans


from collections import defaultdict

class Solution:

	def bfs(self, K, graph):
		indegree = [0] * k
		for i in range(k):
			for adj in graph[i]:
				indegree[adj] += 1
		queue = []
		for i in range(k):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			temp = queue.pop(0)
			ans.append(temp)
			for adj in graph[temp]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					queue.append(adj)
		return ans

	def findOrder(self, alien_dict, N, K):
		graph = defaultdict(list)
		for i in range(1, N):
			str1 = alien_dict[i - 1]
			str2 = alien_dict[i]
			x = 0
			y = 0
			for i in range(min(len(str1), len(str2))):
				if str1[i] != str2[i]:
					graph[ord(str1[i]) - ord('a')].append(ord(str2[i]) - ord('a'))
					break
		ans = self.bfs(K, graph)
		res = []
		for i in ans:
			res.append(chr(i + 97))
		return res


from collections import defaultdict as dq

class Solution:

	def topoSort(self, n, arr):
		q = []
		ind = [0] * n
		for i in range(n):
			for j in arr[i]:
				ind[j] += 1
		for i in range(n):
			if ind[i] == 0:
				q.append(i)
		ptr = 0
		while ptr < len(q):
			for j in arr[q[ptr]]:
				ind[j] -= 1
				if ind[j] == 0:
					q.append(j)
			ptr += 1
		return q

	def check(self, i, j, ans, d):
		for x in range(min(len(i), len(j))):
			if i[x] != j[x]:
				ans[d[i[x]]].append(d[j[x]])
				break

	def findOrder(self, arr, n, k):
		d = dq(int)
		ans = dq(list)
		for i in range(k):
			d[chr(65 + i).lower()] = i
		for i in range(n - 1):
			self.check(arr[i], arr[i + 1], ans, d)
		q = []
		for k in self.topoSort(k, ans):
			q.append(chr(65 + k).lower())
		return ''.join(q)


from collections import deque, defaultdict

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for node in adj[i]:
				indegree[node] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return topo

	def findOrder(self, alien_dict, N, K):
		adj = defaultdict(list)
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			size = min(len(s1), len(s2))
			for j in range(size):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - 97].append(ord(s2[j]) - 97)
					break
		topo = self.topoSort(K, adj)
		ans = ''
		for i in topo:
			ans += chr(i + 97)
		return ans


def get_order(word_list: [], k):
	adj_graph = get_relation_list(word_list, k)
	visited = [False] * k
	data_stack = []
	for i in range(k):
		if not visited[i]:
			dfs_util(i, visited, adj_graph, data_stack)
	final_arr = []
	while len(data_stack) > 0:
		pop_ele = data_stack.pop(-1)
		char_ele = chr(ord('a') + pop_ele)
		final_arr.append(char_ele)
	return final_arr

def dfs_util(vertex: int, visited: [], adj_graph: [[]], data_stack: []):
	if visited[vertex]:
		return
	visited[vertex] = True
	for neighbor in adj_graph[vertex]:
		dfs_util(neighbor, visited, adj_graph, data_stack)
	data_stack.append(vertex)

def get_relation_list(word_list: [], k):
	rel_arr = [[] for i in range(k)]
	i = 0
	n = len(word_list)
	while i < n - 1:
		first_word = word_list[i]
		second_word = word_list[i + 1]
		min_len = min(len(first_word), len(second_word))
		for j in range(min_len):
			if first_word[j] != second_word[j]:
				from_vertex = ord(first_word[j]) - ord('a')
				to_vertex = ord(second_word[j]) - ord('a')
				rel_arr[from_vertex].append(to_vertex)
				break
		i = i + 1
	return rel_arr

class Solution:

	def findOrder(self, alien_dict, N, K):
		return get_order(alien_dict, K)


from collections import deque
from typing import List

class Solution:

	def findOrder(self, alien_dict: List[str], N: int, K: int) -> str:
		adj = [[] for _ in range(K)]
		indegree = [0] * K
		for i in range(N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			length = min(len(s1), len(s2))
			for j in range(length):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					indegree[ord(s2[j]) - ord('a')] += 1
					break
		q = deque()
		for i in range(K):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		if len(topo) != K:
			return ''
		result = ''
		for node in topo:
			result += chr(node + ord('a'))
		return result


from collections import deque

class Solution:

	def findOrder(self, alien_dict, N, K):
		adj = [[] for _ in range(K)]
		for i in range(0, N - 1):
			s1 = alien_dict[i]
			s2 = alien_dict[i + 1]
			ln = min(len(s1), len(s2))
			for j in range(ln):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		V = K
		indegree = [0] * V
		q = deque()
		for i in range(V):
			for it in adj[i]:
				indegree[it] += 1
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		result = ''
		for it in ans:
			result = result + chr(it + ord('a'))
		return result


class Solution:

	def findOrder(self, dic, N, K):
		adj = {}
		for i in range(K):
			adj[i] = []
		for i in range(N - 1):
			(s1, s2) = (dic[i], dic[i + 1])
			l = min(len(s1), len(s2))
			for j in range(l):
				if s1[j] != s2[j]:
					adj[ord(s1[j]) - ord('a')].append(ord(s2[j]) - ord('a'))
					break
		indeg = {}
		for i in range(K):
			indeg[i] = 0
		for i in range(K):
			for x in adj[i]:
				indeg[x] += 1
		from collections import deque
		q = deque()
		for i in range(K):
			if indeg[i] == 0:
				q.append(i)
		top = []
		while q:
			popped = q.popleft()
			top.append(popped)
			for x in adj[popped]:
				indeg[x] -= 1
				if indeg[x] == 0:
					q.append(x)
		res = ''
		for i in top:
			res += chr(i + ord('a'))
		return res