# Longest Word in Dictionary
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-word-in-dictionary)
Canonical: https://scaleengineer.com/dsa/problems/longest-word-in-dictionary
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
Given an array of strings `words` representing an English Dictionary, return _the longest word in_ `words` _that can be built one character at a time by other words in_ `words`.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Note that the word should be built from left to right with each additional character being added to the end of a previous word. 

**Example 1:**

**Input:** words = ["w","wo","wor","worl","world"]
**Output:** "world"
**Explanation:** The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

**Example 2:**

**Input:** words = ["a","banana","app","appl","ap","apply","apple"]
**Output:** "apple"
**Explanation:** Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

**Constraints:**

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

# Approaches
## Brute Force with Set
This approach iterates through every word in the input list. For each word, it checks if it can be "built" by verifying that every one of its prefixes also exists in the input list. To make the prefix lookups efficient, all words are first stored in a HashSet.
**Time:** O(Σ(L_i^2)), where L_i is the length of the i-th word. In the worst case, this is O(N * L^2), where N is the number of words and L is the maximum word length. For each of the N words, we might iterate up to L-1 times to check prefixes. Each prefix check involves a substring operation (O(L)) and a hash set lookup (O(L) for strings). · **Space:** O(S), where S is the total number of characters in all words. This space is used to store the words in the `HashSet`.
**Pros:** Relatively simple to understand and implement.
**Cons:** Inefficient due to the nested loops and repeated prefix checks.; The time complexity is quadratic with respect to word length, which can be slow for long words.
### Explanation
The core idea is to test each word for the "buildable" property. A word is "buildable" if for every length `k` from 1 up to the word's length, the prefix of that length is present in the dictionary.

The algorithm proceeds as follows:
1.  Create a `HashSet` from the input `words` array for fast O(1) average time lookups.
2.  Initialize a string `longestWord` to an empty string. This will store the best result found so far.
3.  Iterate through each `word` in the `words` array.
4.  For the current `word`, check if it's a better candidate for the answer than the current `longestWord`. A word is better if it's longer, or if it's the same length and lexicographically smaller.
5.  If it's a better candidate, we then verify if it's buildable. We assume it is and check all its prefixes from length 1 up to `word.length() - 1`.
6.  If any prefix is not found in the `HashSet`, the word is not buildable. We stop checking this word and move to the next.
7.  If all prefixes are found, the word is confirmed to be buildable, and we update `longestWord` to this word.
8.  After checking all words, `longestWord` holds the final answer.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;

class Solution {
    public String longestWord(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        String result = "";

        for (String word : words) {
            // Check if this word is a potentially better answer
            if (word.length() < result.length() || 
               (word.length() == result.length() && word.compareTo(result) > 0)) {
                continue;
            }
            
            boolean isBuildable = true;
            // Check if all prefixes exist
            for (int k = 1; k < word.length(); k++) {
                if (!wordSet.contains(word.substring(0, k))) {
                    isBuildable = false;
                    break;
                }
            }

            if (isBuildable) {
                result = word;
            }
        }
        return result;
    }
}
```
### Algorithm
*   1. Add all words to a `HashSet` for efficient lookups.
*   2. Initialize `result = ""`.
*   3. For each `word` in the input `words`:
*   4. Check if `word` is a potential candidate (longer than `result`, or same length and lexicographically smaller).
*   5. If it is a candidate, verify if all its prefixes (from length 1 to `length-1`) exist in the `HashSet`.
*   6. If all prefixes exist, update `result = word`.
*   7. Return `result`.

## Sorting and One-Pass Check
This approach improves upon the brute-force method by first sorting the words. By processing words in lexicographical order, we can build up a set of valid "buildable" words incrementally. A word is buildable if it's a single letter long or if its immediate prefix (the word minus its last character) is already in our set of buildable words.
**Time:** O(N * L * log N), where N is the number of words and L is the max word length. The dominant operation is sorting the array of strings. The subsequent loop takes O(N * L) time. · **Space:** O(S), where S is the total number of characters in all words, to store the `builtWords` set. Sorting may also use O(L * log N) or O(N * L) space depending on the implementation.
**Pros:** Much more efficient than the brute-force approach.; The logic is clean and directly leverages the problem's structure.
**Cons:** The sorting step can be a bottleneck if the number of words is very large.
### Explanation
The key insight is that if a word like "apple" is buildable, then all its prefixes ("a", "ap", "app", "appl") must also be buildable and will appear earlier in a lexicographically sorted list. This allows for a much more efficient check.

The algorithm is as follows:
1.  Sort the `words` array lexicographically. This ensures that we process shorter prefixes before the words they build up to (e.g., "ap" before "app").
2.  Create a `HashSet` called `builtWords` to keep track of all the words that have been confirmed to be buildable.
3.  Initialize a string `result` to an empty string.
4.  Iterate through the sorted `words` array.
5.  For each `word`, check if it can be built. This is true if either:
    *   The `word` has a length of 1 (it's a base case).
    *   The prefix of the `word` (i.e., `word.substring(0, word.length() - 1)`) is present in the `builtWords` set.
6.  If the `word` is buildable, it's a valid candidate.
    *   Add the `word` to the `builtWords` set.
    *   Since we are iterating in a way that guarantees we find longer words after their shorter valid counterparts, we just need to check if this new word is longer than our current `result`.
    *   If `word.length() > result.length()`, update `result = word`. The lexicographical tie-breaking is handled automatically by the sort order. The first longest word we encounter will be the lexicographically smallest.
7.  After the loop, `result` will hold the answer.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> builtWords = new HashSet<>();
        String result = "";

        for (String word : words) {
            if (word.length() == 1 || builtWords.contains(word.substring(0, word.length() - 1))) {
                if (word.length() > result.length()) {
                    result = word;
                }
                builtWords.add(word);
            }
        }
        return result;
    }
}
```
### Algorithm
*   1. Sort the `words` array lexicographically.
*   2. Initialize an empty `HashSet` `builtWords` and an empty string `result`.
*   3. For each `word` in the sorted array:
*   4. Check if `word` has length 1 OR if its prefix (`word` minus the last character) exists in `builtWords`.
*   5. If the condition is met, the `word` is buildable.
*   6. Add the `word` to `builtWords`.
*   7. If `word.length() > result.length()`, update `result = word`.
*   8. Return `result`.

## Trie and Search (BFS/DFS)
This is the most optimal approach, leveraging a Trie (prefix tree), a data structure perfectly suited for prefix-related problems. First, all words are inserted into a Trie. Then, a search is performed from the root of the Trie to find the longest path where every node on the path corresponds to a valid word in the dictionary.
**Time:** O(S), where S is the total number of characters in all words. Building the Trie takes O(S). The BFS/DFS traversal visits each node and edge in the Trie at most once, which is also proportional to O(S). · **Space:** O(S), where S is the total number of characters in all words. This space is used to store the Trie. The queue for BFS will, in the worst case, also hold a number of nodes proportional to S.
**Pros:** Most efficient time complexity, linear in the total size of the input.; The Trie is a natural fit for the problem's prefix-based constraints.
**Cons:** More complex to implement than the other approaches due to the need for a custom Trie data structure.
### Explanation
A Trie allows us to efficiently check for the existence of prefixes and build words character by character. The algorithm consists of two main phases:

1.  **Build Trie:**
    *   Define a `TrieNode` class. Each node contains an array of children (for each letter 'a'-'z') and a field to store the complete word if the node marks the end of a word (e.g., `String word = null`).
    *   Iterate through the input `words` and insert each one into the Trie. When a word is fully inserted, store the word itself in the final `TrieNode`.

2.  **Find Longest Word via Search:**
    *   The goal is to find the longest word that is formed by a path from the root where every node on the path has its `word` field set (i.e., represents a complete word from the input).
    *   We can use a Breadth-First Search (BFS). BFS is natural here because it explores words by increasing length.
    *   Initialize a queue and push the `root` of the Trie onto it. The root can be thought of as representing the empty string, which is a valid base.
    *   Initialize `result = ""`.
    *   While the queue is not empty, pop a `node`. This `node` represents a valid, buildable word.
    *   Iterate through the children of the popped `node` (from 'a' to 'z').
    *   If a `child` node exists and has a non-null `word` field (meaning `child.word` is a real word from the input), it's a valid buildable word.
        *   This word is a candidate for our answer. Since BFS explores shorter words before longer ones, any word we find will be either longer than the current `result` or the same length. Because we iterate 'a' through 'z', we will find lexicographically smaller words first for any given length. We update the result if we find a longer word.
        *   Push this `child` node onto the queue to continue searching for even longer words down this path.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.word = w;
        }

        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(root);
        String result = "";

        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            // The node represents a valid buildable word. Check its children.
            for (TrieNode child : node.children) {
                if (child != null && child.word != null) {
                    // This child word is buildable.
                    if (child.word.length() > result.length()) {
                        result = child.word;
                    } else if (child.word.length() == result.length() && child.word.compareTo(result) < 0) {
                        // This check is needed if traversal order doesn't guarantee the lexicographical property, like in DFS.
                        // For BFS, we can simplify, but this is safer.
                        result = child.word;
                    }
                    queue.offer(child);
                }
            }
        }
        return result;
    }
}
```
### Algorithm
*   1. **Build Trie:** Create a Trie and insert all words from the input array. In each node that marks the end of a word, store the word itself.
*   2. **Initialize Traversal:** Create a queue for Breadth-First Search (BFS) and add the `root` node. Initialize `result = ""`.
*   3. **BFS Traversal:**
*   4. While the queue is not empty, dequeue a `node`.
*   5. Iterate through the `node`'s children from 'a' to 'z'.
*   6. If a `child` node exists and represents a complete word (i.e., `child.word` is not null), it means we have found a valid next step in a buildable word. 
*   7. This `child.word` is a valid candidate. Update `result` if it's longer than the current `result`. Since we are exploring level-by-level and lexicographically, the last update for a given length will be the correct one, and longer words are found later.
*   8. Enqueue this `child` for further exploration.
*   9. **Return Result:** After the BFS is complete, `result` will hold the answer.

# Solutions
### Java

```java
class Solution {
private
  Set<String> s;
public
  String longestWord(String[] words) {
    s = new HashSet<>(Arrays.asList(words));
    int cnt = 0;
    String ans = "";
    for (String w : s) {
      int n = w.length();
      if (check(w)) {
        if (cnt < n) {
          cnt = n;
          ans = w;
        } else if (cnt == n && w.compareTo(ans) < 0) {
          ans = w;
        }
      }
    }
    return ans;
  }
private
  boolean check(String word) {
    for (int i = 1, n = word.length(); i < n; ++i) {
      if (!s.contains(word.substring(0, i))) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {string[]} words * @return {string} */ var longestWord = function (
  words,
) {
  const trie = new Trie();
  for (const w of words) {
    trie.insert(w);
  }
  let ans = "";
  for (const w of words) {
    if (
      trie.search(w) &&
      (ans.length < w.length || (ans.length === w.length && w < ans))
    ) {
      ans = w;
    }
  }
  return ans;
};
class Trie {
  constructor() {
    this.children = Array(26).fill(null);
    this.isEnd = false;
  }
  insert(w) {
    let node = this;
    for (let i = 0; i < w.length; i++) {
      const idx = w.charCodeAt(i) - " a ".charCodeAt(0);
      if (node.children[idx] === null) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
    }
    node.isEnd = true;
  }
  search(w) {
    let node = this;
    for (let i = 0; i < w.length; i++) {
      const idx = w.charCodeAt(i) - " a ".charCodeAt(0);
      if (node.children[idx] === null || !node.children[idx].isEnd) {
        return false;
      }
      node = node.children[idx];
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string longestWord(vector<string> &words) {
    unordered_set<string> s(words.begin(), words.end());
    int cnt = 0;
    string ans = "";
    for (auto w : s) {
      int n = w.size();
      if (check(w, s)) {
        if (cnt < n) {
          cnt = n;
          ans = w;
        } else if (cnt == n && w < ans)
          ans = w;
      }
    }
    return ans;
  }
  bool check(string &word, unordered_set<string> &s) {
    for (int i = 1, n = word.size(); i < n; ++i)
      if (!s.count(word.substr(0, i)))
        return false;
    return true;
  }
};

```

### Python

```python
class Solution:
    def longestWord(self, words: List[str]) -> str: cnt, ans = 0, '' s = set(words) for w in s: n = len(w) if all(w[: i] in s for i in range(1, n)): if cnt < n: cnt, ans = n, w elif cnt == n and w < ans: ans = w return ans

```