Watch 5 video solutions for Longest Word With All Prefixes, a medium level problem involving Depth-First Search, Trie. This walkthrough by take U forward has 123,058 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |