Derive Alien Character Order - Intuit Online Assessment IGDTUW

Problem Preview

"You are given a dictionary of words sorted according to the rules of an unknown alien language. Using the sorted dictionary, determine a **valid ordering** of the alien alphabet. If multiple valid orderings exist, return the **lexicographically smallest** valid ordering. If the dictionary is invalid (contains a contradiction), print: ```text INVALID ``` A contradiction occurs when: * A **cycle** exists in the character dependencies. * A **longer word appears before its own prefix**. --- ## Input Format * The first line contains an integer **N**, representing the number of words. * The second line contains **N** space-separated words representing the dictionary order. --- ## Output Format Print: * A string representing the **lexicographically smallest valid character ordering**, or * `INVALID` if no valid ordering exists. --- ## Constraints * `1 ≤ N ≤ 10^5` * Total number of characters across all words ≤ `10^5` --- ## Sample Input ```text 5 baa abcd abca cab cad ``` ## Sample Output ```text bdac ``` --- ## Explanation From the given dictionary: * `baa` → `abcd` gives `b < a` * `abcd` → `abca` gives `d < a` * `abca` → `cab` gives `a < c` * `cab` → `cad` gives `b < d` These constraints produce the ordering: ```text b < d < a < c ``` Hence, the lexicographically smallest valid ordering is: ```text bdac ``` If a cycle exists or a word appears before its own prefix (e.g., `abcd` before `ab`), the output should be: ```text INVALID ``` ---"