DSA interview question

Longest Word With All Prefixes

Medium · Data structures · Topics: trie, hash map, sorting

The problem

You're building a predictive text/autocomplete validator for a keyboard app. A word should only ever appear as a fully-typeable suggestion if every "intermediate stage" of typing it (every prefix) was also a valid, previously-seen word — this ensures the autocomplete tree never suggests a word the user couldn't have naturally arrived at by typing character-by-character through other valid words. Given an array of strings words, find the longest word such that every prefix of that word (of every length) also exists in words. If there's a tie in length, return the lexicographically smallest one. If no such word exists, return an empty string.

Example: words = ["w","wo","wor","worl","world"] → "world", since every prefix ("w","wo","wor","worl") is also present.

Function signature

string longestWordWithAllPrefixes(vector<string>& words);

Test cases

Input `words`	Output	Explanation
`["w","wo","wor","worl","world"]`	`"world"`	All prefixes of "world" exist in the array
`["a","banana","app","appl","ap","apply","apple"]`	`"apple"`	"a","ap","app","appl","apple" all exist; "apply" also valid but "apple" wins (tie-break: lexicographically smaller, or check actual lengths)
`["abc","bc","b","empty"]`	`""`	"abc" requires "a","ab" to exist — they don't; "bc" requires "b" — exists, but "bc" itself needs further check; no valid full chain found
`["a"]`	`"a"`	Single character is trivially its own only prefix
`["yo","ew","fc","zrc","yodn","fcm","qm","qmz","zrc","fc","ewq","yod"]`	`"yodn"`	Classic LeetCode example
`[]`	`""`	Empty input
`["xyz"]`	`""`	"xyz" has no prefixes "x" or "xy" present, so it's invalid

(Always verify exact outputs by running the algorithm — manual prefix-chasing is error-prone for larger examples.)

How interviewers phrase it

"Find the longest word in this list such that every prefix of it is also in the list."
"Build a word, one character at a time — at every step, that partial word must already exist in the given list. What's the longest complete word you can build this way?"
This is LeetCode 720 ("Longest Word in Dictionary") — interviewers often frame it as a Trie problem to test whether you recognize when a Trie's structure (parent-child = prefix relationship) is the natural fit, versus just brute-force checking prefixes with a hash set.

Clarifying questions to ask

If there are multiple words of the same maximum length satisfying the condition, which should I return? (Standard convention: lexicographically smallest — confirm this explicit tie-breaking rule.)
Does a single-character word automatically qualify (since it has no smaller non-empty prefix to check)? (Yes — a single char word is trivially valid, its only "prefix" is itself.)
Can words contain duplicates? (Shouldn't affect correctness but good to confirm — duplicates would just be redundant insertions into whatever structure I build.)
What's the expected size of words and individual word lengths? (Determines whether O(total characters) Trie approach is necessary vs. naive prefix-checking with a hash set being "good enough.")
Are all words guaranteed to be non-empty, lowercase-only strings?

Follow-ups to expect

"What's the brute-force/hash-set approach, and what's its complexity?"
"How does the Trie approach improve this, and why is it a natural fit?"
"Walk through why DFS over the Trie + tracking 'all prefixes are valid words' as you descend gives you the correct longest word in O(total characters) instead of O(n * maxLen²)."
"How would you handle the tie-breaking (lexicographically smallest) cleanly within a Trie DFS?"
"Could you solve this with sorting instead of a Trie, and what's the tradeoff?"
"What if you needed to return ALL longest valid words, not just one?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview