Skip to main content

269. Alien Dictionary

hard

Given a list of words sorted lexicographically in an alien language, deduce a valid ordering of its letters. Reduces to topological sort on the letter-ordering graph built from adjacent-word character mismatches — with two famous edge cases that catch most candidates.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return ''. If there are multiple solutions, return any of them.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of only lowercase English letters.

Examples

Example 1

Input
words = ['wrt','wrf','er','ett','rftt']
Output
'wertf'

Example 2

Input
words = ['z','x']
Output
'zx'

Example 3

Input
words = ['z','x','z']
Output
''

Explanation: The order is invalid, so return ''.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Adjacent words give you ordering edges. Compare words[i] and words[i+1] char by char; first mismatch (a, b) means a -> b.

Hint 2

Watch the prefix edge case: if words[i+1] is a strict prefix of words[i] (e.g., 'abc' before 'ab'), the input is invalid — return ''.

Hint 3

Build the directed graph, then topo-sort with Kahn's. If the topo order length != number of distinct letters, a cycle exists — return ''.

Solution approach

Reveal approach

Build a directed graph over every distinct letter that appears anywhere. For each adjacent pair (words[i], words[i+1]), find the first position where the characters differ; that gives an edge first_char -> second_char. Track edges in a set per source to dedupe. If no mismatch is found within the shorter length and words[i].length > words[i+1].length, return '' — that's the prefix violation ('abc' can't precede 'ab' in any sane lexicographic order). Then topological-sort the graph with Kahn's BFS: compute in-degrees, seed the queue with 0-in-degree letters, pop and append to result, decrement neighbors. If the final result string contains every distinct letter, return it. Otherwise a cycle blocked some letters — return ''. O(C) time where C is the total number of characters across all words.

Complexity

Time
O(C) where C = total chars
Space
O(1) — bounded by 26 letters

Related patterns

  • topological-sort
  • bfs
  • dfs
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Meta
  • Amazon
  • Airbnb

Practice these live with InterviewChamp.AI

Drill Alien Dictionary and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →