Skip to content
RED SAGSkills
hard60 ptstopological-sortgraph

Recover an Unknown Alphabet

An archive uses a language written with lowercase English letters, but in an unknown alphabetical order. You are given words, a list that is claimed to be sorted according to that order (the usual dictionary rule: compare at the first differing letter; a word comes before any longer word it is a prefix of).

Return a string containing every letter that appears in words exactly once, in an order consistent with the list. Several orders may be consistent; return the one that is smallest in normal a-to-z comparison, which you get by always placing the smallest available letter next. If no order is consistent (contradictions, or a word listed before its own prefix), return "".

Example 1

Input: words = ["bca","bcd","ab","aa"]
Output: "bacd"
Explanation: b must come before a and a before d; c is free, so the smallest valid order is "bacd".

Example 2

Input: words = ["z","x","z"]
Output: ""
Explanation: z before x and x before z is a contradiction.

Constraints

  • 1 <= words.length <= 3000
  • 1 <= words[i].length <= 10
  • Lowercase letters only
Hint 1

Compare each pair of neighbouring words: the first differing letters give one ordering rule.

Hint 2

Run a topological sort, always choosing the smallest letter with no remaining incoming rules; if you get stuck before placing every letter, there is a cycle.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Full Stack Developer, AI Engineer (LLM & Generative AI), Data Scientist, Automation Test Engineer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.