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

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:

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

This is essentially checking if a word can be built incrementally by other words in the list.
We can either:
- Build a Trie and do DFS
- Or use a set and iterate words after sorting
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

Sort words:
- By length (shortest first)
- For same length, by lexicographical order
Use a set to track valid words that can be built.
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
Track the longest valid word seen so far.

✅ 4. JavaScript Code (Clean & Commented)

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

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

After sorting:

["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.

Longest Word In Dictionary