Given an array of strings words, find the longest string in words such that every prefix of it is also in words.
words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".
Example 1:
Input: words = ["k","ki","kir","kira", "kiran"] Output: "kiran" Explanation: "kiran" has prefixes "kira", "kir", "ki", and "k", and all of them appear in words.
Example 2:
Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] Output: "apple" Explanation: Both "apple" and "apply" have all their prefixes in words. However, "apple" is lexicographically smaller, so we return that.
Example 3:
Input: words = ["abc", "bc", "ab", "qwe"] Output: ""
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 1051 <= sum(words[i].length) <= 105words[i] consists only of lowercase English letters.Problem Overview: You are given a list of words. The goal is to return the longest word such that every prefix of that word also appears in the list. For example, if "apple" exists, then "a", "ap", "app", and "appl" must also exist. If multiple valid answers exist, return the lexicographically smallest one.
Approach 1: Hash Set Prefix Validation (O(n * L^2) time, O(n) space)
Store all words in a HashSet for constant-time lookup. For each word, check every prefix by iterating from length 1 to L and verifying it exists in the set. If all prefixes exist, compare the word with the current best answer (prefer longer length, then lexicographically smaller). The key operation is repeated substring creation and hash lookup for each prefix, which leads to O(L^2) work per word in many languages. This approach is easy to implement and works well when word lengths are small.
Approach 2: Trie with Prefix Validation (O(n * L) time, O(n * L) space)
Insert every word into a Trie. Each node stores children characters and a flag indicating whether a word ends at that node. After building the Trie, validate words by walking through their characters and ensuring every node along the path represents a completed word. Because each character traversal is constant time, prefix validation becomes O(L). This avoids repeated substring creation and leverages the prefix structure directly.
You can also perform a Depth-First Search on the Trie starting from the root. Only traverse nodes whose isWord flag is true, ensuring every prefix is valid. Track the longest word encountered during traversal. DFS naturally builds prefixes character by character and ensures invalid branches are pruned early.
The Trie approach scales better when the dataset contains many words with shared prefixes. Prefix validation becomes a simple pointer traversal instead of repeated hash lookups and substring creation.
Recommended for interviews: The Trie solution is the expected approach. It demonstrates strong understanding of prefix trees and efficient prefix validation. Starting with the HashSet solution shows clear reasoning about the problem constraints, but implementing a Trie shows stronger algorithmic depth and familiarity with common interview data structures.
We define a Trie where each node has two attributes: a child node array children of length 26, and a flag isEnd indicating whether the node marks the end of a word.
We iterate over words, and for each word w, we traverse from the root node. If the child node array of the current node does not contain the first character of w, we create a new node, then continue traversing the next character of w. After traversing all characters of w, we set the isEnd flag of the current node to \texttt{true}.
Next, we iterate over words again, and for each word w, we traverse from the root node. If the isEnd field of a node in the child node array is \texttt{false}, it means some prefix of w is not in words, and we return \texttt{false}. Otherwise, we continue traversing the next character of w, and after traversing all characters, we return \texttt{true}.
The time complexity is O(sum_{w \in words} |w|), and the space complexity is O(sum_{w \in words} |w|), where |w| is the length of word w.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set Prefix Check | O(n * L^2) | O(n) | Simple implementation when word lengths are small |
| Trie with Prefix Validation | O(n * L) | O(n * L) | Optimal solution when many words share prefixes |
| Trie + DFS Traversal | O(n * L) | O(n * L) | Useful when building the answer directly during traversal |
L3. Longest Word With All Prefixes | Complete String | Trie • take U forward • 123,058 views views
Watch 4 more video solutions →Practice Longest Word With All Prefixes with our built-in code editor and test cases.
Practice on FleetCode