Foreign Alphabet Order (Hard) — Practice with Code Visualizer

You are exploring documents from an ancient civilization that uses a writing system based on the English alphabet. However, the order of letters in their alphabet differs completely from the standard English order — and this ordering is unknown to you.

Fortunately, you have access to a lexicon containing a list of words that are already sorted in lexicographical order according to this civilization's alphabet rules.

Your task is to analyze the lexicon and deduce the correct ordering of the letters. Return a string containing all unique letters that appear in the lexicon, arranged according to the correct alphabetical order of this foreign language.

Important considerations:

If the given word ordering is logically inconsistent (i.e., no valid letter ordering could produce this sequence), return an empty string "".
If multiple valid orderings exist based on the given information, you may return any one of them.
The comparison follows standard lexicographical rules: words are compared character by character from left to right, and the first differing character determines the relative order. If one word is a prefix of another, the shorter word comes first.

Analyzing adjacent words: From "wrt" and "wrf", we learn t < f. From "wrf" and "er", we learn w < e. From "er" and "ett", we learn r < t. From "ett" and "rftt", we learn e < r. Combining these constraints through topological ordering yields: w → e → r → t → f, so the answer is "wertf".

With only two single-character words, the only constraint is z < x, giving us "zx".

From "z" and "x", we get z < x. From "x" and "z", we get x < z. These constraints contradict each other (z < x and x < z cannot both be true), so no valid ordering exists and we return "".

Fortunately, you have access to a lexicon containing a list of words that are already sorted in lexicographical order according to this civilization's alphabet rules.

Important considerations:

If the given word ordering is logically inconsistent (i.e., no valid letter ordering could produce this sequence), return an empty string "".
If multiple valid orderings exist based on the given information, you may return any one of them.
The comparison follows standard lexicographical rules: words are compared character by character from left to right, and the first differing character determines the relative order. If one word is a prefix of another, the shorter word comes first.

With only two single-character words, the only constraint is z < x, giving us "zx".

From "z" and "x", we get z < x. From "x" and "z", we get x < z. These constraints contradict each other (z < x and x < z cannot both be true), so no valid ordering exists and we return "".

Foreign Alphabet Order

Hints

Foreign Alphabet Order

Hints