hardGraphsAI-applied~45 min
Infer Token Precedence Order
A tokenizer emitted a vocabulary sorted by an unknown custom alphabet. From the sorted list of tokens, recover a valid ordering of the underlying symbols so downstream sorting can be reproduced.
Problem
Given a list of words sorted lexicographically by an unknown alphabet, return any valid ordering of the distinct characters. If the ordering is invalid (contradictory or a prefix violation), return an empty string.
Input
An array words of n strings (1 ≤ n ≤ 100), lowercase letters, total length ≤ 10^4.
Output
A string giving one valid character order, or "" if none exists.
Constraints
- Only lowercase English letters appear
- Return "" if a word precedes its own prefix (e.g. 'abc' before 'ab')
- Any valid topological order is accepted
Examples
Example 1
Input
words = ["wrt","wrf","er","ett","rftt"]
Output
"wertf"
Adjacent comparisons yield edges t→f, w→e, r→t, e→r, giving order w,e,r,t,f.
Example 2
Input
words = ["abc","ab"]
Output
""
A longer word cannot precede its own prefix — invalid.