# Longest Word In Dictionary

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:**

```plaintext
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:**

```plaintext
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".
```

  
Let’s tackle **“Longest Word in Dictionary”** step-by-step in your structured interview format – clear, elegant, and optimized. 🙌

---

### ✅ 1. Problem Explanation (In Simple Terms)

You’re given a list of words (dictionary).

You need to find the **longest word** that can be built **one character at a time** by other words in the dictionary.

👉 For a word to be valid:

* All of its **prefixes** must also exist in the dictionary.
    

📘 Example:

```js
Input: ["w","wo","wor","worl","world"]
Output: "world" 
// because "w" → "wo" → "wor" → "worl" → "world" are all in the list
```

If there are multiple answers of the same length, **return the one that is lexicographically smallest**.

---

### 💡 2. Key Insights

1. This is essentially checking if a word can be **built incrementally** by other words in the list.
    
2. We can either:
    
    * Build a **Trie** and do DFS
        
    * Or use a **set** and iterate words **after sorting**
        
3. Sorting words helps:
    
    * To check prefixes in order
        
    * To ensure that **shortest prefixes come first**
        
    * To naturally resolve **lexicographical tie-breaking**
        

---

### 🧠 3. Steps to Solve

1. Sort words:
    
    * By length (shortest first)
        
    * For same length, by lexicographical order
        
2. Use a **set to track valid words** that can be built.
    
3. For each word in sorted list:
    
    * If `word.length === 1` → add to set
        
    * Else if `word.slice(0, word.length - 1)` is in the set → it can be built → add to set
        
4. Track the longest valid word seen so far.
    

---

### ✅ 4. JavaScript Code (Clean & Commented)

```javascript
/**
 * @param {string[]} words
 * @return {string}
 */
function longestWord(words) {
  // Sort words by length, then lexicographically
  words.sort((a, b) => {
    if (a.length === b.length) return a.localeCompare(b);
    return a.length - b.length;
  });

  const valid = new Set();
  let result = "";

  for (const word of words) {
    if (word.length === 1 || valid.has(word.slice(0, word.length - 1))) {
      valid.add(word);

      // Update result if it's longer or lexicographically smaller
      if (
        word.length > result.length ||
        (word.length === result.length && word < result)
      ) {
        result = word;
      }
    }
  }

  return result;
}
```

---

### 🔍 5. Dry Run Example

Input:

```js
["a", "banana", "app", "appl", "ap", "apply", "apple"]
```

After sorting:

```js
["a", "ap", "app", "appl", "apple", "apply", "banana"]
```

Processing:

* "a" → valid
    
* "ap" (prefix "a") → valid
    
* "app" (prefix "ap") → valid
    
* "appl" (prefix "app") → valid
    
* "apple" (prefix "appl") → valid ✅ current best
    
* "apply" (prefix "appl") → valid but same length as "apple", "apple" is smaller
    
* "banana" → "banan" not valid → skip
    

✅ Final Result = `"apple"`

---

### ⏱️ 6. Time & Space Complexity

Let `n = number of words`, `L = average word length`

* **Sorting:** O(n log n)
    
* **Loop + slice:** O(n × L)
    
* **Space:** O(n) for the set
    

> ✅ **Time Complexity:** O(n × L + n log n)  
> ✅ **Space Complexity:** O(n)

---

### ✅ Final Verdict

* Fast, simple, and elegant set-based solution.
    
* Trie-based version is also valid but overkill for this version of the problem.
    
* Works great with large dictionaries.