def foreignDictionary(self, words: List[str]) -> str:
        
        # Why Topological Sort?
        # Each character -> node in directed graph
        # Edge (c1 -> c2) means -> c1 comes before c2 in alien dictionary
        # Topological sort -> Finding a valid order of characters
        # Finding a valid order of characters is equivalent to performing
        # a topological sort on this graph.
        # If cycle exists, no valid order exists

        # Note:
        # 1. Build a graph of character dependencies from adjacent words
        # 2. Count in-degrees for each character
        # 3. Use BFS to perform topological sort
        # 4. Detect cycles: if result length != total unique chars, return ""

        # Initialize graph and in-degree counts
        graph = defaultdict(set)  # char -> set of chars that come after it
        in_degree = {c: 0 for word in words for c in word}

        # Build graph edges based on adjacent words
        for i in range(len(words) - 1):
            word1, word2 = words[i], words[i+1]
            min_len = min(len(word1), len(word2))
            found_diff = False

            for j in range(min_len):
                c1, c2 = word1[j], word2[j]
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        in_degree[c2] += 1
                    found_diff = True
                    break

            # Edge case: prefix situation invalid, e.g., "abc" before "ab"
            if not found_diff and len(word1) > len(word2):
                return ""

        # BFS topological sort
        queue = deque([c for c in in_degree if in_degree[c] == 0])
        result = []

        while queue:
            c = queue.popleft()
            result.append(c)
            for nei in graph[c]:
                in_degree[nei] -= 1
                if in_degree[nei] == 0:
                    queue.append(nei)

        # Check for cycle
        if len(result) != len(in_degree):
            return ""

        res = "".join(result)


        # overall: time complexity O(C + W*L)
        # C = number of unique characters, W = number of words, L = average word length
        # overall: space complexity O(C + W*L) for graph and in-degree
        return res