'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from collections import defaultdict, Counter, deque

'''
In a valid alphabet, prefixes are always first, e.g., "ab" then "abcd"
'''

# educative.io version
# build the graph of characters by comparing adjacent words
# then perform topological sort to determine the order
# O(V+E) – where V is the number of vertices and E is the number of edges in the graph.
def alienOrder(self, words: List[str]) -> str:
    if not words:
        return ""
    # initialize
    inDegree = {} # all characters
    graph = {} # we don't know all the vertices
    for word in words:
        for c in word:
            inDegree[c] = 0
            graph[c] = []
    # build the graph
    for i in range(len(words)-1):
        w1, w2 = words[i], words[i+1]
        for j in range(min(len(w1), len(w2))):
            parent, child = w1[j], w2[j]
            if parent != child:
                graph[parent].append(child)
                inDegree[child] += 1
                # break the inner for loop, will still continue the outer for loop
                break # only the first different character between the two words will help us find the order
        else:
            if len(w2) < len(w1): # w1: "abc", w2: "ab"
                return ""

    # find all sources
    sources = deque()
    for c, ct in inDegree.items():
        if ct == 0:
            sources.append(c)

    sortedOrder = []
    while sources:
        c = sources.popleft()
        sortedOrder.append(c)
        for child in graph[c]:
            inDegree[child] -= 1
            if inDegree[child] == 0:
                sources.append(child)

    if len(sortedOrder) != len(inDegree):
        return ""
    return "".join(sortedOrder)


class Solution:
    # T: O(C), C be the total length of all the words in the input list, 
    # added together.
    # Let N be the total number of strings in the input list.
    # U be the total number of unique letters in the alien alphabet.
    # S: O(1) or O(U + min(U^2, N )). BFS solution, similar to topological sort
    def alienOrder(self, words: List[str]) -> str:
        # Step 0: create data structures + the in_degree of each unique 
        # letter to 0.
        adj_list = defaultdict(set)
        in_degree = Counter({c : 0 for word in words for c in word})
        
        # Step 1: We need to populate adj_list and in_degree.
        # For each pair of adjacent words...
        for w1, w2 in zip(words, words[1:]):
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in adj_list[c1]:
                        adj_list[c1].add(c2) # c1 -> c2
                        in_degree[c2] += 1
            # break and check next pair of words since each pair can only tell
            # us information about two letters. if c2 already in adj_list[c1],
            # we break immediately, that's why break is aligned with if
                    break # go to the next loop of "for w1, w2..."
            # notice here using "else" is because we are done looping the 
            # zip(w1, w2) and the loop is not break, then it goes into "else"
            else: # Check that second word isn't a prefix of first word.
                if len(w2) < len(w1): # "abc", "ab"
                    return ""
        
        # Step 2: We need to repeatedly pick off nodes with an indegree of 0.
        output = []
        queue = deque([c for c in in_degree if in_degree[c] == 0])
        while queue:
            c = queue.popleft()
            output.append(c)
            for d in adj_list[c]:
                in_degree[d] -= 1
                if in_degree[d] == 0:
                    queue.append(d)
                    
        # If not all letters are in output, that means there was a cycle 
        # and so no valid ordering.
        # Return "" as per the problem description.
        if len(output) < len(in_degree):
            return ""
        # Otherwise, convert the ordering we found into a string and return it.
        return "".join(output)
    
    
    # DFS version
    '''
    The order in which nodes are returned by the depth-first search will be the 
    reverse of a valid alphabet order.
    Remember that when we reverse the edges of a directed graph, the nodes with no 
    incoming edges became the ones with no outgoing edges. This means that the ones
     at the start of the alphabet will now be the ones returned first.
    '''
    def alienOrder1(self, words: List[str]) -> str:
    
        # Step 0: Put all unique letters into the adj list.
        reverse_adj_list = {c : [] for word in words for c in word}
    
        # Step 1: Find all edges and put them in reverse_adj_list.
        for first_word, second_word in zip(words, words[1:]):
            for c, d in zip(first_word, second_word):
                if c != d: 
                    reverse_adj_list[d].append(c) # lexi order: c -> d
                    break
            else: # Check that second word isn't a prefix of first word.
                if len(second_word) < len(first_word): 
                    return ""
    
        # Step 2: Depth-first search.
        seen = {} # False = grey, True = black.
        output = []
        def visit(node):  # Return True iff there are no cycles.
            if node in seen: # could be grey or black
                return seen[node] # If this node was grey (False), a cycle was detected.
            seen[node] = False # Mark node as grey, being visited
            for next_node in reverse_adj_list[node]:
                result = visit(next_node)
                if not result: 
                    return False # Cycle was detected lower down.
            seen[node] = True # Mark node as black.
            output.append(node)
            return True
    
        if not all(visit(node) for node in reverse_adj_list):
            return ""
    
        return "".join(output)
    
        
        
sol = Solution()
print (sol.alienOrder(["wrt","wrf","er","ett","et","rftt"]))
    
    
    
    
    
    
    