Longest Word With All Prefixes

Longest Word With All Prefixes

What is this problem about?

The Longest Word With All Prefixes coding problem asks you to analyze an array of strings and find the longest string such that every single prefix of that string is also present in the array. If there is a tie for the longest string, return the one that appears earliest lexicographically. It is essentially identical to "Longest Word in Dictionary" but explicitly phrased around prefix validation.

Why is this asked in interviews?

This problem is a direct assessment of a candidate's ability to build and navigate a Trie (Prefix Tree). While Hash Set solutions work, companies like Google ask this specific variant to force candidates into implementing tree-based data structures. It tests your understanding of node traversal, flag setting (isEndOfWord), and recursive string building.

Algorithmic pattern used

The absolute best pattern for this is the Trie.

1. Build a Trie and insert every word from the array. Mark the last node of each word with a boolean flag (e.g., isWord = true).
2. Traverse the Trie using Depth-First Search (DFS).
3. The golden rule for traversal: You may only visit a child node if its isWord flag is true! This ensures that every prefix leading up to the current character is a valid word in the array. Track the longest path found during this DFS.

Example explanation

Array: ["a", "b", "c", "ab", "bc", "abc"] Construct the Trie. Nodes marked * are valid words:

• Root -> a* -> b* -> c*
• Root -> b* -> c*
• Root -> c*

Traverse via DFS:

• Go down a*. Valid. Path: "a".
• From a*, go down to b*. Valid. Path: "ab".
• From b*, go down to c*. Valid. Path: "abc". Max length is 3.
• What if we trace b* -> c*? Path "bc" length 2. The longest word built strictly through valid nodes is "abc". If "ab" was missing from the array, the b node under a would not be marked isWord, so the DFS would stop at "a", failing to reach "abc".

Common mistakes candidates make

When using the Trie DFS approach, candidates often struggle with the lexicographical tie-breaker. A brilliant trick to avoid messy string comparisons after the DFS is to iterate through the Trie children from 'z' down to 'a' (or vice-versa depending on how you update your max variable). If you evaluate 'a' before 'z', and strictly use > (greater than) for length updates, the lexicographically smaller string naturally wins ties.

Interview preparation tip

When preparing for the Longest Word With All Prefixes interview question, commit the basic Trie node class to memory. It should contain a map or array of children (Node[26]) and a boolean isWord. Being able to code a Trie insertion method fluidly in under two minutes gives you massive confidence and leaves you plenty of time to focus on the DFS logic.