Decode the Glyph Order
HardGraphs
Problem
An archaeologist found a glossary written in an unknown script. Its glyphs have been transcribed as lowercase letters, but the script's alphabet order is not the usual one. The glossary's words are known to be sorted according to that unknown order (shorter words come before longer words that start with them).
Return a string containing every distinct letter that appears in words, arranged in an order consistent with the glossary. When several orders are consistent, return the one that is smallest in ordinary a–z comparison: at each position, choose the smallest letter that can legally come next. If no order is consistent, return an empty string.
Example 1
- Input:
- words = ["dc", "da", "ca", "cb"]
- Output:
- "dcab"
dc < da gives c before a; da < ca gives d before c; ca < cb gives a before b.
Example 2
- Input:
- words = ["zx", "zy", "w"]
- Output:
- "xyzw"
Only x before y and z before w are known; at each step the smallest free letter is placed.
Example 3
- Input:
- words = ["xy", "x"]
- Output:
- ""
A word can never come before its own prefix.
Constraints
- 1 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 100
- words[i] contains only lowercase English letters.
Hint
Show the first hint
Two neighbouring words in a sorted list tell you something about at most one pair of letters. Which pair?
Walkthrough
How to approach it
01Clarify before coding
- Which letters must appear in the answer? Every distinct letter in any word, even letters with no known relation.
- Is a prefix after its extension valid, like ["xy", "x"]? No: return "".
- Why only adjacent pairs? Sortedness is transitive; comparing non-adjacent words adds no new information.
02Brute force
Try every permutation of the distinct letters in a–z lexicographic order and return the first one under which the words are sorted.
Cost: Up to 26! permutations, each checked in O(total length): astronomically slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.