Show problems as
Classic problem #269HardArrayStringDepth-First SearchBreadth-First SearchGraph TheoryTopological SortDirected Acyclic Graph

Alien Dictionary

Real-world version: Lost Collation Order
Tracked in this browser only
Read Alien Dictionary on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstDirected Acyclic Graph (DAG) Traversal · Graphs, animated step by step

A retired records system stored its index keys under a custom collation: someone had fixed a private ranking of the symbols, and the system sorted keys by comparing symbols left to right using that ranking, exactly the way a dictionary works. The only surviving artefact is keys, a dump of the index already sorted under that collation, in non-decreasing order. The ranking table itself is gone.

Each key is written with lowercase English letters used as symbols. Rebuild the ranking: return a string that holds every distinct symbol appearing in keys exactly once, written from lowest rank to highest.

A dump usually pins down only part of the ranking, so more than one string can explain it. When that happens, return whichever of those strings comes first when they are compared as ordinary English text. If no ranking of the symbols could have produced the given dump, return an empty string.

Examples

Example 1

Input
keys = ["cb", "ca", "ab"]
Output
"bca"

The first two keys share their opening symbol, so `b` outranks `a` below `c`; the last two show `c` outranks `a` at the opening symbol. That forces `b` and `c` ahead of `a`, and `bca` is the first such string in ordinary text order.

Example 2

Input
keys = ["kite", "kits", "sun"]
Output
"eiknstu"

The dump only reveals that `e` precedes `s` and that `k` precedes `s`. Every other symbol floats freely, so the earliest ordinary-text string honouring those two facts wins.

Example 3

Input
keys = ["dip", "di"]
Output
""

A key cannot be listed ahead of one of its own openings, whatever the ranking is, so nothing explains this dump.

Constraints

  • 1 <= keys.length <= 100
  • 1 <= keys[i].length <= 100
  • keys[i] consists of lowercase English letters only
  • Return the string that comes first in ordinary English text order among all rankings consistent with keys, or "" when none is consistent

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def collation_order(keys: list[str]) -> str:
Java
public String collationOrder(String[] keys)

More on the same topics