#720 Longest Word in Dictionary

frequently reported atMicrosoft Amazon

the problem

In plain words

Find the longest word in the list whose every prefix ("w", "wo", "wor", …) is also a word in the list, so it grows one letter at a time through valid words. On a tie, pick the alphabetically smallest; if nothing qualifies, return "".

in words = ["w","wo","wor","worl","world"]

out "world"

in words = ["a","banana","app","appl","ap","apply","apple"]

out "apple"

"apply" also works but "apple" is smaller.

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 30
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)

"Every prefix is a word" means: in a trie, every node on the path is an end-of-word node. DFS the trie but only step into end-of-word children; the deepest node reached is the answer.

solutions

From brute force to optimal

For each word, check that all its prefixes are in a set; keep the best by (length, then alphabetical).

dict = HashSet of words.
For each word: all prefixes of length 1..L−1 in dict?
Update best if longer, or equal length and smaller.

timeO(Σ L²)

Up to L prefixes per word, each substring + hash costing O(L).

spaceO(S)

The set.

javajava.util.*

1class Solution {2    public String longestWord(String[] words) {3        Set<String> dict = new HashSet<>(Arrays.asList(words));4        String best = "";5        for (String w : words) {6            boolean buildable = true;7            for (int len = 1; len < w.length() && buildable; len++) {8                buildable = dict.contains(w.substring(0, len)); // every prefix must be a word9            }10            if (!buildable) continue;11            if (w.length() > best.length() || (w.length() == best.length() && w.compareTo(best) < 0)) {12                best = w;13            }14        }15        return best;16    }17}

After sorting, every prefix comes before its extensions; a word is buildable if it has length 1 or its word-minus-last-letter was buildable.

Sort words.
If length 1 or built contains w minus last char → add to built.
Keep the first longest (sorted order handles ties).

timeO(n log n · L)

The sort dominates; each check is one O(L) substring + hash.

spaceO(S)

The set of buildable words.

javajava.util.*

1class Solution {2    public String longestWord(String[] words) {3        String[] sorted = words.clone();4        Arrays.sort(sorted);                       // shorter prefixes come before their extensions5        Set<String> built = new HashSet<>();6        String best = "";7        for (String w : sorted) {8            if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {9                built.add(w);10                if (w.length() > best.length()) best = w; // ties: earlier = smaller, keep it11            }12        }13        return best;14    }15}

Insert all words; DFS from the root visiting children a→z, entering a child only if a word ends there.

Build the trie, storing the word at its end node.
DFS: for each child in a..z with child.word != null, update best if longer, recurse.

timeO(S)

Each letter is inserted once; the DFS visits each node at most once (26 slot checks each — a constant).

spaceO(S·26)

Trie nodes; recursion depth ≤ 30.

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        String word; // non-null when a word ends here5    }6 7    private String best = "";8 9    public String longestWord(String[] words) {10        Node root = new Node();11        for (String w : words) {12            Node cur = root;13            for (char ch : w.toCharArray()) {14                int i = ch - 'a';15                if (cur.children[i] == null) cur.children[i] = new Node();16                cur = cur.children[i];17            }18            cur.word = w;19        }20        best = "";21        dfs(root);22        return best;23    }24 25    /** Only step into children that are themselves words — that is "built one letter at a time". */26    private void dfs(Node node) {27        for (Node child : node.children) {            // 'a'..'z': first longest is the smallest28            if (child == null || child.word == null) continue;29            if (child.word.length() > best.length()) best = child.word;30            dfs(child);31        }32    }33}

in the room

How to say it in the interview

talk track

Point out the tie-break comes free: a→z DFS order = lexicographic order, and we only replace on strictly longer.

traps

Replacing the best on equal length — that picks the lexicographically larger word.
Forgetting that single-letter words are buildable on their own (the empty prefix is implied).

what they ask next

Follow-ups

Return every buildable word, not just the longest?

Run the same DFS and collect the word at every node you enter. Each node is visited once, so it stays O(S).

Can you do it without recursion?

BFS over word nodes, children a→z. Each level then comes out in alphabetical order, so the first word on the deepest level is the answer.

before you submit

Edge cases to test

No one-letter word in the list → nothing can be built: return "".
Two answers of the same length → the alphabetically smaller one.
A gap in the chain ("moc" missing) → "mocha" can't be built.

practise next