Skip to main content
Talentd

Longest Word With All Prefixes - Solution & Explanation

MediumPremiumFree on FleetCodeDepth-First SearchTrie16 min readAsked at: Google
Practice this problem

Problem Statement

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

  • For example, let 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 <= 105
  • 1 <= words[i].length <= 105
  • 1 <= sum(words[i].length) <= 105
  • words[i] consists only of lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Set Prefix CheckO(n * L^2)O(n)Simple implementation when word lengths are small
Trie with Prefix ValidationO(n * L)O(n * L)Optimal solution when many words share prefixes
Trie + DFS TraversalO(n * L)O(n * L)Useful when building the answer directly during traversal

Video Solution

1858. Longest Word With All Prefixes - Week 4/5 Leetcode September Challenge • Programming Live with Larry • 263 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Longest Word With All Prefixes easy or hard?
The problem is typically classified as Medium difficulty. The core idea is straightforward once you recognize the prefix requirement, but implementing a Trie and validating prefixes efficiently requires familiarity with string data structures.
Longest Word With All Prefixes Python/Java solution
Most implementations build a Trie class and insert every word. After insertion, validate words by checking that each prefix node marks a complete word. The same logic works in Python, Java, C++, Go, and TypeScript with O(n * L) complexity.
How to solve Longest Word With All Prefixes in O(n * L)?
Build a Trie containing all words. While validating a word, traverse the Trie character by character and check that every node on the path has the 'isWord' flag set. Because each character is processed once, validation takes O(L) per word, giving a total complexity of O(n * L).
What is the best approach for Longest Word With All Prefixes?
The most efficient approach uses a Trie. Insert all words into the Trie and ensure that every node along a word's path represents a valid word. This guarantees that all prefixes exist. The algorithm runs in O(n * L) time where n is the number of words and L is the maximum word length.
Is Longest Word With All Prefixes asked at Google/Amazon/Meta?
Prefix-based string problems using Tries frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of prefix trees, efficient string lookup, and traversal strategies.
What data structure is used in Longest Word With All Prefixes?
The primary data structure is a Trie (prefix tree). It allows efficient storage of words and fast prefix validation by traversing characters through linked nodes.
What is the time complexity of Longest Word With All Prefixes?
The optimal Trie-based solution runs in O(n * L) time because each word is inserted once and each prefix check traverses at most L characters. Space complexity is O(n * L) due to storing all characters in the Trie structure.

Ready to solve this problem?

Practice Longest Word With All Prefixes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Word in Dictionary