How should I practice Infer a Lexicographically Smallest Alien Alphabet?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Infer a Lexicographically Smallest Alien Alphabet associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · String

Infer a Lexicographically Smallest Alien Alphabet

Learn this problem

● Hard

MicrosoftFULLTIMEONSITE INTERVIEW

See Microsoft hiring insights

Problem statement

An alien language uses the lowercase English letters, but their order is unknown. You receive an array words sorted according to that language.

Infer a character order that is consistent with the dictionary. Include every distinct character that appears in words exactly once.

If several orders are valid, return the lexicographically smallest valid order.
If a longer word appears before its exact prefix, or the inferred precedence rules contain a cycle, return the empty string.

Function

alienOrder(words: String[]) → String

Examples

Example 1

words = ["wrt","wrf","er","ett","rftt"]return = "wertf"

The adjacent words imply w < e < r < t < f, so the order is unique.

Example 2

words = ["za","zb","ca","cb"]return = "abzc"

The rules require a < b and z < c; choosing the smallest available character at each step gives abzc.

Example 3

words = ["abc","ab"]return = ""

A longer word cannot precede its exact prefix in a valid sorted dictionary.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
Every word contains only lowercase English letters.
The total number of characters is at most 10^4.