Longest Word in Dictionary

Medium
654.

Longest Word in Dictionary

Longest Word in Dictionary is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Word in Dictionary — Solution in Python, Java & C++

Longest Word in Dictionary solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Word in Dictionary is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Trie
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Longest Word in Dictionary

  1. Hint 1

    A word qualifies when all of its proper prefixes are in the dictionary.

  2. Hint 2

    Put the words in a set so each prefix test is O(1).

  3. Hint 3

    Keep a running champion under the rule 'longer wins, then lexicographically smaller wins'.

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

Java

public static String longestWord(String[] words) {
    Set<String> have = new HashSet<>(Arrays.asList(words));
    String best = "";
    for (String w : words) {
        boolean ok = true;
        for (int len = 1; len < w.length(); len++) {
            if (!have.contains(w.substring(0, len))) { ok = false; break; }
        }
        if (!ok) continue;
        if (w.length() > best.length() || (w.length() == best.length() && w.compareTo(best) < 0)) best = w;
    }
    return best;
}

C++

string longestWord(vector<string>& words) {
    unordered_set<string> have(words.begin(), words.end());
    string best = "";
    for (const string& w : words) {
        bool ok = true;
        for (size_t len = 1; len < w.size(); len++) {
            if (!have.count(w.substr(0, len))) { ok = false; break; }
        }
        if (!ok) continue;
        if (w.size() > best.size() || (w.size() == best.size() && 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets