Solution Approach: Topological Sort The problem can be modeled as finding a topological ordering of the characters. Build a Graph: Identify all unique characters present in the words list. Iterate through adjacent pairs of words (word1, word2). Find the first position where the characters differ. The character in word1 comes before the character in word2 in the alien alphabet. Add a directed edge from the first character to the second in your graph (e.g., t -> f). Crucial check: If word1 is a prefix of word2 (e.g., "app" before "apple") this is valid. If word2 is a prefix of word1 (e.g., "apple" before "app") and they share the same prefix, the dictionary is invalid, and you should immediately return an empty string.