Katkat
Back

Reconstruct the Alphabet Order of an Alien Language

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to model partial ordering constraints using a directed graph and perform a topological sort to deduce a valid sequence.

Problem Statement

You are given a list of non-empty words from an alien language which uses the same 26 lowercase English letters as our alphabet. However, the order of these letters is unknown. You are given that the words are sorted lexicographically according to the rules of this alien language.

Write a function findAlienOrder(words) that returns a string of the unique letters in the alien language sorted in the order defined by the input list. If there is no valid order, return an empty string. If there are multiple valid orders, return any one of them.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • Words contain only lowercase English letters.

Examples

Example 1: Input: words = ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf" Explanation:

  • 'w' < 'e' (from "wrt" vs "er")
  • 'r' < 't' (from "wrt" vs "wrf")
  • 't' < 'f' (from "wrf" vs "er")
  • 'e' < 'r' (from "er" vs "ett")

Example 2: Input: words = ["z", "x", "z"] Output: "" Explanation: The order is invalid because 'z' cannot be both before and after 'x'.

Function Signature

def findAlienOrder(words: list[str]) -> str:

Hints

Hint 1

Model the letters as nodes in a graph and derive directed edges based on the first differing character between adjacent words in the sorted list.

Hint 2

Use Kahn's algorithm or Depth First Search (DFS) to perform a topological sort on the graph of dependencies.

Hint 3

Remember to handle cases where no valid topological sort exists, such as when a cycle is detected in the graph.

Follow-up questions

  • How would you modify your solution to handle cases where a word is a prefix of another word (e.g., ["abc", "ab"]) which violates the sorted order?
  • What is the time and space complexity of your solution in terms of the number of words (N) and the average length of each word (L)?
  • How would you ensure that characters present in the input but not involved in any ordering constraints are still included in the final result?