Longest Word in Dictionary — Medium Problem & Solution

Problem statement

Return the longest word in words that can be built one character at a time by other words in words — that is, every proper prefix of it is also in words.

If several words tie on length, return the lexicographically smallest. If none qualifies, return the empty string.

Example 1

Input: words = ["w","wo","wor","worl","world"]
Output: world
Explanation: Every prefix of "world" is present.

Example 2

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: apple
Explanation: "apple" and "apply" both qualify at length 5; "apple" is lexicographically smaller.

Example 3

Input: words = ["abc","bc","c"]
Output: c
Explanation: "abc" needs "a" and "ab", which are missing.

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• words[i] consists of lowercase English letters.

How to solve Longest Word in Dictionary

The build-up condition is purely about prefixes, so a set membership test per prefix decides each word. A single pass keeping the best word under the stated ordering then finds the answer.

Approach

1. Insert every word into a hash set.
2. For each word, test each proper prefix (lengths 1 through len - 1) for membership; a single miss disqualifies it.
3. Among the qualifying words, keep the longest, breaking ties by taking the lexicographically smaller.

Why it works

If every proper prefix is present, the word can be reached by adding one letter at a time starting from its one-letter prefix — and conversely, any such build-up visits exactly those prefixes. The trie solution encodes the same test structurally and runs faster on large dictionaries.

Complexity

• Time — O(total characters) with a set, or O(total characters) with a trie
• Space — O(total characters)

Pitfalls

• Testing the word itself as a prefix always succeeds and tells you nothing — stop at len - 1.
• Comparing with >= on length without the tie-break returns whichever tied word came last in the input.

Reference solution

Python

from typing import List

def longestWord(words: List[str]) -> str:
    have = set(words)
    best = ""
    for w in words:
        if any(w[:i] not in have for i in range(1, len(w))):
            continue
        if len(w) > len(best) or (len(w) == len(best) and w < best):
            best = w
    return best

JavaScript

var longestWord = function(words) {
    var have = {};
    for (var i = 0; i < words.length; i++) have[words[i]] = true;
    var best = "";
    for (var j = 0; j < words.length; j++) {
        var w = words[j], ok = true;
        for (var len = 1; len < w.length; len++) {
            if (have[w.substr(0, len)] !== true) { ok = false; break; }
        }
        if (!ok) continue;
        if (w.length > best.length || (w.length === best.length && w < best)) best = w;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium