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.

Description Hints 2 Solution Video 7:32

1858. Longest Word With All Prefixes

Medium73.1% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
1 <= words[i].length <= 10⁵
1 <= sum(words[i].length) <= 10⁵
words[i] consists only of lowercase English letters.

Asked at 1 company

Google

Topics

Depth-First Search Trie

Hints open one at a time

Hint 1

Add all the words to a trie.

Hint 2

Check the longest path where all the nodes are words.

7:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution