Alien Dictionary
Updated
Problem statement
A new language uses lowercase English letters, but the order of its letters is unknown to you.
You are given a list of strings words that is said to be sorted in the dictionary order of this language. Two words are compared letter by letter. At the first position where they differ, the word with the earlier letter comes first. If one word is a prefix of the other, the shorter word comes first.
Return a string that contains every distinct letter appearing in words exactly once, in an order under which words is sorted. If no such order exists, return an empty string "".
If several orders work, return the one that comes first in normal alphabetical order when the answers are compared as ordinary strings.
Function
alienOrder(words: String[]) → StringExamples
Example 1
words = ["bca", "aaa", "acb"]return = "bac"The first letters of "bca" and "aaa" differ, so b comes before a. The words "aaa" and "acb" first differ at their second letter, so a comes before c.
The only order of a, b and c that follows both rules is "bac".
Example 2
words = ["dog", "cat", "cow"]return = "adcgotw"From "dog" and "cat", d comes before c. From "cat" and "cow", a comes before o. Nothing is known about g, t or w.
Many orders work. The one that comes first alphabetically starts with a, then d. Now c is allowed and is the smallest letter left, so it comes next, followed by g, o, t and w. The answer is "adcgotw".
Example 3
words = ["abc", "ab"]return = ""The word "ab" is a prefix of "abc", so it would have to come first. No letter order can fix this, so the answer is "".
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i]consists of only lowercase English letters.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Alien DictionaryByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Infer a Lexicographically Smallest Alien AlphabetMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Alien DictionaryBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Alien DictionaryAmazon · ONSITE INTERVIEW
- Recover an Alien Alphabet from Sorted WordsOpenAI · PHONE SCREENOpenAI interview questions
- Alien Dictionary OrderGoogle · PHONE SCREENGoogle interview questions
- Letter Order from a Sorted Word ListRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Evaluate Formulas with Cycle DetectionInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Validate CSV References and Field DependenciesStripe · PHONE SCREENStripe interview questions
- Password From Ordering HintsRogo · ONSITE INTERVIEW