Longest Buildable Word

You are given an array of lowercase strings words.

A word is buildable when it can be grown one character at a time, left to right, with every intermediate string also present in words. Equivalently: every proper prefix of the word, from length 1 up to its full length minus one, must itself appear in words.

Return the longest buildable word. If several buildable words tie for longest, return the lexicographically smallest of them. If none is buildable, return the empty string "".

Note that a word of length 1 has no proper prefixes, so it is always buildable.

Examples

Example 1

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: Each prefix of "world" is present, so the whole word can be grown one letter at a time.

Example 2

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apple" and "apply" are buildable through "a", "ap", "app", "appl", and both have length 5. "apple" is the lexicographically smaller of the two. "banana" is not buildable because "b" is absent.