Problem Description

Given an array of strings words, your task is to find the longest word in words such that every prefix of the word is also in words. A prefix of a word is any substring that starts at the beginning of the word and ends at any position before or at the end. For example, for the word "apple", the prefixes are "a", "ap", "app", "appl", and "apple".

If there are multiple answers with the same length, return the lexicographically smallest one. If there is no such word, return an empty string.

Constraints:

• Each word consists of lowercase English letters only.
• All strings in words are unique.
• There is at most one valid answer.

Thought Process

To solve this problem, we first need to recognize that the main challenge is checking, for each word, whether all of its prefixes are present in the input list. A brute-force approach would be to check every word and, for each, verify all its prefixes by scanning the list. However, this would be inefficient, especially for large lists or long words.

To optimize, we can use a data structure that allows for fast prefix lookups, such as a set (hash set). This way, we can check if a prefix exists in constant time. Next, we realize that we want the longest word with all prefixes present, and if there are ties, the lexicographically smallest.

We also notice that if we process words in a sorted order (by length, then lexicographically), we can efficiently track which words are "buildable" from their prefixes. This insight leads us toward a more efficient solution.

Solution Approach

Let's break down the optimized solution step by step:

1. Store all words in a set: This allows for O(1) lookups to check if a prefix exists.
2. Sort the list of words: Sort the words first by length (shortest to longest), then lexicographically. This ensures that we always consider shorter prefixes before longer words, and in case of ties, the lexicographically smaller word comes first.
3. Iterate through sorted words: For each word, check if all its prefixes (excluding the whole word itself) exist in the set.
4. Track the best candidate: If a word satisfies the prefix condition and is longer (or lexicographically smaller in case of a tie) than the current answer, update the answer.
5. Return the answer: After processing all words, return the best candidate found, or an empty string if none is valid.

This approach is efficient because:

• Set lookups are O(1).
• Sorting is O(N log N), where N is the number of words.
• We only check up to L prefixes per word, where L is the word's length.

Example Walkthrough

Input: words = ["w","wo","wor","worl","world","banana","ban","bana","banan"]

1. Store all words in a set for fast lookup.
2. Sort words: ["w", "wo", "ban", "wor", "bana", "worl", "banan", "world", "banana"]
3. For each word:
   • "w": All prefixes ("") exist (trivially true), so "w" is a candidate.
   • "wo": Prefix "w" exists, so "wo" is a candidate (longer than "w").
   • "ban": Prefixes: "b", "ba" — neither in the set, so skip.
   • "wor": Prefixes: "w", "wo" — both exist, so "wor" is now the best candidate.
   • "bana": Prefixes: "b", "ba", "ban" — "ban" exists, but "b" and "ba" do not, so skip.
   • "worl": Prefixes: "w", "wo", "wor" — all exist, so "worl" is now the best candidate.
   • "banan": Prefixes: "b", "ba", "ban", "bana" — "ban" and "bana" exist, but "b" and "ba" do not, so skip.
   • "world": Prefixes: "w", "wo", "wor", "worl" — all exist, so "world" is now the best candidate.
   • "banana": Prefixes: "b", "ba", "ban", "bana", "banan" — "ban", "bana", "banan" exist, but "b" and "ba" do not, so skip.
4. The answer is "world", since all its prefixes are present and it is the longest such word.

Code Implementation

class Solution:
    def longestWord(self, words):
        words_set = set(words)
        words.sort()
        ans = ""
        for word in sorted(words, key=lambda w: (len(w), w)):
            valid = True
            for i in range(1, len(word)):
                if word[:i] not in words_set:
                    valid = False
                    break
            if valid:
                if len(word) > len(ans):
                    ans = word
        return ans
      

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        sort(words.begin(), words.end());
        string ans = "";
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() == b.length() ? a < b : a.length() < b.length();
        });
        for (const string& word : words) {
            bool valid = true;
            for (int i = 1; i < word.size(); ++i) {
                if (wordSet.find(word.substr(0, i)) == wordSet.end()) {
                    valid = false;
                    break;
                }
            }
            if (valid && word.length() > ans.length()) {
                ans = word;
            }
        }
        return ans;
    }
};
      

import java.util.*;
class Solution {
    public String longestWord(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Arrays.sort(words);
        Arrays.sort(words, (a, b) -> a.length() != b.length() ? a.length() - b.length() : a.compareTo(b));
        String ans = "";
        for (String word : words) {
            boolean valid = true;
            for (int i = 1; i < word.length(); ++i) {
                if (!wordSet.contains(word.substring(0, i))) {
                    valid = false;
                    break;
                }
            }
            if (valid && word.length() > ans.length()) {
                ans = word;
            }
        }
        return ans;
    }
}
      

var longestWord = function(words) {
    const wordSet = new Set(words);
    words.sort();
    words.sort((a, b) => a.length === b.length ? a.localeCompare(b) : a.length - b.length);
    let ans = "";
    for (let word of words) {
        let valid = true;
        for (let i = 1; i < word.length; ++i) {
            if (!wordSet.has(word.substring(0, i))) {
                valid = false;
                break;
            }
        }
        if (valid && word.length > ans.length) {
            ans = word;
        }
    }
    return ans;
};
      

Time and Space Complexity

Brute-force approach: For each word of length L, check all prefixes by scanning the list (O(N) per prefix). For all words, this is O(N * L * N), which is inefficient for large N.

Optimized approach:

• Sorting: O(N log N), where N is the number of words.
• For each word, checking all prefixes: O(L) per word, where L is the word's length.
• Set lookups: O(1) per prefix check.
• Total: O(N log N + N * L)

This is efficient and suitable for the input constraints.

Summary

The key insight for this problem is to use a set for O(1) prefix lookups and to process words in a sorted order so that we always build up from shorter prefixes. This avoids unnecessary re-checks and ensures that we find the longest, lexicographically smallest word with all prefixes present. The final solution is both simple and efficient, leveraging basic data structures and sorting.