Problem 19.5 · TrieMedium

Longest Word in Dictionary

PatternTrie (Prefix Tree)Tree DFS Hash Map Lookup (Complement)

What it teaches: DFS over a trie, moving only through nodes that end words.

Practise it on judges as “Longest Word in Dictionary”.

The problem

Return the longest word that can be built one letter at a time, where every prefix is also in the list. On a tie, return the lexicographically smallest. Return "" if none.

Example 1

Input: words = [a, banana, app, appl, ap, apply, apple]
Output: "apple"

apply and apple both qualify; apple is smaller.

Constraints

1 ≤ words ≤ 1000
1 ≤ length ≤ 30

Pattern clues in the wording

→ Every prefix must exist
→ Longest, then smallest

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String longestWord(String[] words) {
        return "";
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	words = ["w","wo","wor","worl","world"]	"world"
2	words = ["a","banana","app","appl","ap","apply","apple"]	"apple"
3	words = ["abc","bc"]	""

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Trie DFS through word nodes · O(total characters)2. Sort + hash set · O(n log n × L)

Trie DFS through word nodes

Time O(total characters) Space O(total characters)

Insert all words storing each at its end node. DFS from the root visiting children a to z, but only into nodes that hold a word. Track the longest word found.

Approach 1

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word;
    }

    private String best = "";

    public String longestWord(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node n = root;
            for (char c : w.toCharArray()) {
                if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
                n = n.next[c - 'a'];
            }
            n.word = w;
        }
        dfs(root);
        return best;
    }

    private void dfs(Node n) {
        for (Node child : n.next) {
            if (child == null || child.word == null) continue;
            if (child.word.length() > best.length()) best = child.word;
            dfs(child);
        }
    }
}

Verdict: Alphabetical DFS handles the tie-break for free.

Sort + hash set

Time O(n log n × L) Space O(total characters)

Sort the words. Walk them in order; a word is buildable if its prefix without the last letter is already in the buildable set (or it has length 1).

Approach 2

import java.util.*;

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> built = new HashSet<>();
        String best = "";
        for (String w : words) {
            if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
                built.add(w);
                if (w.length() > best.length()) best = w;
            }
        }
        return best;
    }
}

Verdict: Short to write.

Before you submit

Edge cases and common mistakes

Test these inputs

No single-letter words (answer "")
Ties in length

Mistakes people make

Replacing the answer on equal length (breaks the lexicographic tie-break).

Interview

Follow-up questions

Why does sorting make the hash-set version correct?