384. Alien Dictionary - Order of Characters

An alien language uses the first k lowercase English letters (a, b, c, ... up to the k-th). Given n words from this language already sorted according to the alien lexicographic order (and guaranteed consistent with some valid ordering, with no word being an exact prefix continuation issue to worry about), determine that order. Print the k characters in order, space-separated; if the given words are contradictory (no valid order exists), print 'Invalid'.

Input: The first line contains an integer k, the alphabet size. The second line contains an integer n, the number of words. Each of the next n lines contains one word using only the first k lowercase letters. Output: Print the k characters of the alien alphabet in order, space-separated, or print 'Invalid' if no valid order exists.

1 <= k <= 26, 1 <= n <= 1000

If the topological sort can't successfully order ALL k characters (some remain stuck with unresolved in-degree), that's a direct signal of a genuine contradiction in the given sorted word list - Kahn's algorithm's own 'stuck' condition doubles as the 'Invalid' detection here.

Given words from an alien language already sorted according to some unknown alphabet order, determine that order. Brute force: Try every possible permutation of the k characters and check if it's consistent with all the given words' sorted order - this is factorial time, impractical, when extracting direct 'comes before' relationships and topologically sorting them is far more efficient. Optimised: Each pair of consecutive sorted words reveals EXACTLY ONE precedence relationship (at their first differing character) - collecting all these relationships as directed edges and running topological sort directly reconstructs the alphabet order, with Kahn's algorithm's cycle-detection naturally identifying CONTRADICTORY input as an 'Invalid' case.

Build the same constraint graph as before, but use Kahn's algorithm properly: first push all letters with in-degree 0 into a queue in one initial pass, then repeatedly pop a letter from the queue, append it to the result order, and decrement the in-degree of each of its neighbors, pushing any neighbor whose in-degree drops to 0 onto the queue. If the final result contains fewer than k letters, a cycle exists and the order is 'Invalid'. This finds the exact same valid ordering as the naive repeated-scan approach but processes every node and edge exactly once using the queue to track which nodes are ready, avoiding the repeated full scans for in-degree-0 nodes. Time: O(n * L + k) Space: O(k)

Gather the same ordering constraints as before by comparing adjacent words, and build them into a directed graph over the k letters with an edge from an earlier letter to a later one plus an in-degree count for each letter. Then repeatedly scan through all remaining letters to find one with in-degree 0, output it, remove it from the graph, and decrement its neighbors' in-degrees, continuing until no letters remain (or declaring 'Invalid' if at some point no in-degree-0 letter can be found while letters remain, indicating a cycle). This replaces exhaustive permutation testing with a genuine topological sort, but repeatedly scanning all remaining nodes to find the next in-degree-0 one each time adds unnecessary overhead. Time: O(n * L + k^2) Space: O(k)

Compare each pair of lexicographically adjacent words character by character to find the first position where they differ, which gives an ordering constraint (the character in the earlier word must come before the character in the later word). After collecting all such constraints, try every one of the k! possible orderings of the alphabet's k letters and check which permutation satisfies all of the collected constraints. This conceptually simple approach is guaranteed to find a valid order if one exists, but testing every permutation of even a modest number of letters is computationally infeasible. Time: O(n * L + k!) Space: O(k^2)

1. Compare each pair of CONSECUTIVE words and find the FIRST position where their characters differ - that reveals one character must come immediately BEFORE the other in the alien alphabet, giving a directed edge. 2. Once you have all such 'comes before' edges, this is exactly TOPOLOGICAL SORT - use Kahn's algorithm with a min-priority-queue so ties resolve to the alphabetically-smallest character. 3. If the topological sort can't include ALL k characters (some still have unresolved dependencies at the end), the ordering is contradictory - print 'Invalid'.

Time: O(total characters across all words + k) - comparing consecutive word pairs takes time proportional to their length, plus a linear topological sort over the k characters. Space: O(k), for the precedence graph among the k alien characters.

contradictory word orderings that make the topological sort impossible (print 'Invalid'), k = 1, and n at its maximum of 1000 to confirm the topological sort with tie-breaking runs efficiently.

Be ready to mention that the standard word-comparison rule also handles the tricky case where one word is a PREFIX of another (e.g. 'abc' before 'ab' would be invalid, since a shorter prefix must always come first if no other letters differ) - though this problem's constraints explicitly guarantee this issue doesn't arise, it's worth knowing as a real-world edge case of this problem family.