Longest Word With All Prefixes
01 · Problem
You are given an array of strings words. A word is buildable if every one of its non-empty prefixes (including the word itself) also appears in words. For example, "cat" is buildable only if "c", "ca" and "cat" are all in the array.
Return the longest buildable word. If several buildable words share the maximum length, return the one that is lexicographically smallest. If no word is buildable, return the empty string "".
02 · Examples
words = ["m","mo","moo","moon","moons"]
"moons"
Every prefix of "moons" ("m", "mo", "moo", "moon") is in the list, and it is the longest such word.
words = ["t","to","top","tops","tap","ta","taps","tip","tipsy"]
"taps"
"tops" and "taps" are both buildable with length 4, and "taps" is lexicographically smaller. "tipsy" is not buildable because "ti" is missing.
words = ["dog","og","do","go"]
""
"dog" and "do" need "d", "og" needs "o", and "go" needs "g". None of those are present, so no word is buildable.
03 · Constraints
- 011 <= words.length <= 105
- 021 <= words[i].length <= 105
- 031 <= sum(words[i].length) <= 105
- 04words[i] consists of lowercase English letters only
04 · Optimal complexity
- Time
- O(S)
- Space
- O(S)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.