165. Longest Word in Dictionary

🔗 LeetCode Problem: 720. Longest Word in Dictionary
📊 Difficulty: Medium
🏷️ Topics: Trie, Array, String, Hash Table, Sorting

Problem Statement

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 letter 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

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving:

Input: ["w", "wo", "wor", "worl", "world"]

Question: Which word can be built step-by-step?

Check "w":
  Length 1 → Always valid (base case) ✓

Check "wo":
  Need "w" in dictionary? YES ✓
  Can build: w → wo ✓

Check "wor":
  Need "wo" in dictionary? YES ✓
  Can build: w → wo → wor ✓

Check "worl":
  Need "wor" in dictionary? YES ✓
  Can build: w → wo → wor → worl ✓

Check "world":
  Need "worl" in dictionary? YES ✓
  Can build: w → wo → wor → worl → world ✓

Result: "world" (longest word with complete chain)

KEY INSIGHT: Must have ALL prefixes in dictionary! 🔑

What Makes a Word Valid:

VALID word requirements:
  1. ALL prefixes must exist in dictionary
  2. Built ONE character at a time
  3. From left to right only

Example: "apple"
  Prefixes needed:
    "a"     → must exist ✓
    "ap"    → must exist ✓
    "app"   → must exist ✓
    "appl"  → must exist ✓
    "apple" → final word ✓

If ANY prefix missing → INVALID!

Example: "banana" with dictionary ["a", "banana"]
  Prefix "b" needed → NOT in dictionary ✗
  Cannot build "banana" → INVALID!

Multiple Candidates - Lexicographical Order:

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

Find all valid words:

Check "a":
  Length 1 → Valid ✓

Check "ap":
  Need "a"? YES ✓
  Valid ✓

Check "app":
  Need "ap"? YES ✓
  Valid ✓

Check "appl":
  Need "app"? YES ✓
  Valid ✓

Check "apple":
  Need "appl"? YES ✓
  Valid ✓ (length 5)

Check "apply":
  Need "appl"? YES ✓
  Valid ✓ (length 5)

Check "banana":
  Need "b"? NO ✗
  Invalid!

Valid candidates: ["a", "ap", "app", "appl", "apple", "apply"]

Both "apple" and "apply" have length 5:
  "apple" < "apply" (lexicographically)

Result: "apple" ✓

Why Trie is Perfect:

APPROACH 1: Brute Force (HashSet)
For each word:
  Check if all prefixes exist in set
  Track longest valid word

Problem:
  - For each word of length k, check k prefixes
  - Each prefix check: O(k) to create substring
  - O(n * k²) time - inefficient!

APPROACH 2: Trie (Optimal)
Build Trie with all words
For each word in Trie:
  Check if ALL ancestors have isEndOfWord = true
  Natural prefix chain verification!

Benefits:
  - Build once: O(n * k)
  - Check each word: O(k)
  - Total: O(n * k) - LINEAR! 🚀
  - No substring creation needed
  - Lexicographical order naturally maintained

---

🧠 The AHA Moment - Why Trie Wins

The Trie Structure with "All Prefixes" Property:

Words: ["w", "wo", "wor", "worl", "world"]

Build Trie:
                    root
                     |
                    [w] ← isEnd = true (word "w")
                     |
                    [o] ← isEnd = true (word "wo")
                     |
                    [r] ← isEnd = true (word "wor")
                     |
                    [l] ← isEnd = true (word "worl")
                     |
                    [d] ← isEnd = true (word "world")

Check "world":
  Path: root → w → o → r → l → d

  At 'w': isEnd? YES ✓ (word "w" exists)
  At 'o': isEnd? YES ✓ (word "wo" exists)
  At 'r': isEnd? YES ✓ (word "wor" exists)
  At 'l': isEnd? YES ✓ (word "worl" exists)
  At 'd': isEnd? YES ✓ (word "world" exists)

  ALL nodes marked → "world" is VALID! ✓

The Trie SHOWS us the complete prefix chain! 🎯

Compare Valid vs Invalid:

CASE 1: Valid Word
Words: ["a", "ap", "app", "appl", "apple"]

Trie:
        root
         |
        [a] ← isEnd = true
         |
        [p] ← isEnd = true
         |
        [p] ← isEnd = true
         |
        [l] ← isEnd = true
         |
        [e] ← isEnd = true

Check "apple":
  Every node on path has isEnd = true ✓
  Result: VALID!

CASE 2: Invalid Word
Words: ["a", "apple"]  (missing "ap", "app", "appl")

Trie:
        root
         |
        [a] ← isEnd = true
         |
         p  ← isEnd = false ✗
         |
         p  ← isEnd = false ✗
         |
         l  ← isEnd = false ✗
         |
        [e] ← isEnd = true

Check "apple":
  At 'p': isEnd = false ✗
  Missing prefix! Result: INVALID!

The Trie makes it VISIBLE which prefixes are missing! 🔍

The DFS Search Strategy:

Why DFS on Trie?

Starting from root, we explore:
  - Only paths where EVERY node has isEnd = true
  - Builds words character by character
  - Naturally finds longest valid words
  - Lexicographical order from left-to-right traversal

DFS Template:
  1. If current node NOT isEnd → STOP (invalid chain)
  2. If current node IS isEnd → Continue exploring children
  3. Track longest valid word found
  4. Visit children in alphabetical order (a to z)

This ensures:
  - All prefixes are valid
  - Longest word found
  - Lexicographically smallest when tied

Visual DFS Walkthrough:

Words: ["w", "wo", "wor", "worl", "world", "a"]

Trie:
                  root
                 /    \
               [a]    [w]
                       |
                      [o]
                       |
                      [r]
                       |
                      [l]
                       |
                      [d]

DFS Exploration (alphabetical order):

Start at root, word = ""

Branch 1: Explore 'a'
  node = 'a', word = "a"
  isEnd? YES ✓
  Has children? NO
  Valid word: "a" (length 1)

Branch 2: Explore 'w'
  node = 'w', word = "w"
  isEnd? YES ✓
  Has children? YES
  Valid word: "w" (length 1)

  Go deeper to 'o':
    node = 'o', word = "wo"
    isEnd? YES ✓
    Has children? YES
    Valid word: "wo" (length 2)

    Go deeper to 'r':
      node = 'r', word = "wor"
      isEnd? YES ✓
      Has children? YES
      Valid word: "wor" (length 3)

      Go deeper to 'l':
        node = 'l', word = "worl"
        isEnd? YES ✓
        Has children? YES
        Valid word: "worl" (length 4)

        Go deeper to 'd':
          node = 'd', word = "world"
          isEnd? YES ✓
          Has children? NO
          Valid word: "world" (length 5) ✓✓

          This is the LONGEST! Return "world"

Result: "world" 🎯

---

🎯 Solution Approaches

Approach 1: Brute Force with HashSet

Idea: For each word, check if all prefixes exist in set.

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

        for (String word : words) {
            // Check if all prefixes exist
            if (isValid(word, wordSet)) {
                // Update result based on length and lexicographical order
                if (word.length() > result.length() || 
                    (word.length() == result.length() && word.compareTo(result) < 0)) {
                    result = word;
                }
            }
        }

        return result;
    }

    private boolean isValid(String word, Set<String> wordSet) {
        // Check all prefixes from length 1 to length-1
        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            if (!wordSet.contains(prefix)) {
                return false;
            }
        }
        return true;
    }
}

Analysis: - Time Complexity: O(n * k²) where n = words, k = avg word length (substring creation) - Space Complexity: O(n * k) for HashSet - Pros: Simple to understand - Cons: Creates many substring objects, inefficient for long words

---

Approach 2: Sorting + HashSet

Idea: Sort words by length, build up valid words incrementally.

class Solution {
    public String longestWord(String[] words) {
        // Sort by length, then lexicographically
        Arrays.sort(words, (a, b) -> {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }
            return a.compareTo(b);
        });

        Set<String> built = new HashSet<>();
        built.add("");  // Empty string as base
        String result = "";

        for (String word : words) {
            // Check if prefix (word without last char) exists
            String prefix = word.substring(0, word.length() - 1);
            if (built.contains(prefix)) {
                built.add(word);
                // Since sorted, longer/lexico-smaller comes later
                if (word.length() > result.length()) {
                    result = word;
                }
            }
        }

        return result;
    }
}

Analysis: - Time Complexity: O(n * k * log n) for sorting + O(n * k) for processing = O(n * k * log n) - Space Complexity: O(n * k) for HashSet - Pros: Cleaner logic, processes in order - Cons: Sorting overhead, still creates substrings

---

Approach 3: Trie + DFS (Optimal Solution) ⭐

Idea: Build Trie, then DFS to find longest valid word.

class Solution {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
        String word = null;  // Store the complete word at end nodes
    }

    private TrieNode root = new TrieNode();

    public String longestWord(String[] words) {
        // Step 1: Build Trie with all words
        for (String word : words) {
            insert(word);
        }

        // Step 2: DFS to find longest valid word
        return dfs(root, new StringBuilder());
    }

    private void insert(String word) {
        TrieNode node = root;

        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }

        node.isEndOfWord = true;
        node.word = word;  // Store complete word
    }

    private String dfs(TrieNode node, StringBuilder current) {
        String longest = "";

        // If current node itself represents a valid word
        if (node.word != null) {
            longest = node.word;
        }

        // Explore all children in alphabetical order
        for (int i = 0; i < 26; i++) {
            TrieNode child = node.children[i];

            // CRITICAL: Only explore if child is end of word
            // This ensures ALL prefixes exist!
            if (child != null && child.isEndOfWord) {
                current.append((char)('a' + i));
                String candidate = dfs(child, current);
                current.deleteCharAt(current.length() - 1);

                // Update longest based on length, then lexicographically
                if (candidate.length() > longest.length() ||
                    (candidate.length() == longest.length() && 
                     candidate.compareTo(longest) < 0)) {
                    longest = candidate;
                }
            }
        }

        return longest;
    }
}

Alternative Implementation (Simpler):

class Solution {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;  // Only set for complete words
    }

    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();

        // Build Trie
        for (String word : words) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.word = word;  // Mark end of word
        }

        // DFS starting from root
        return dfs(root);
    }

    private String dfs(TrieNode node) {
        String longest = node.word == null ? "" : node.word;

        // Try all children in order (a to z)
        for (int i = 0; i < 26; i++) {
            TrieNode child = node.children[i];

            // KEY: Only continue if child represents a complete word
            // This ensures the prefix chain is unbroken!
            if (child != null && child.word != null) {
                String candidate = dfs(child);

                // Update if candidate is longer or same length but lexico-smaller
                if (candidate.length() > longest.length() ||
                    (candidate.length() == longest.length() && 
                     candidate.compareTo(longest) < 0)) {
                    longest = candidate;
                }
            }
        }

        return longest;
    }
}

Analysis: - Time Complexity: O(n * k) where n = words, k = avg word length - Build Trie: O(n * k) - DFS: O(n * k) - visits each node once - Space Complexity: O(n * k) for Trie structure - Pros: Optimal time, no substring creation, natural lexicographical order - Cons: More complex, requires understanding of Trie + DFS

---

📝 Detailed Dry Run

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

PHASE 1: Build Trie

═══════════════════════════════════════════════
BUILD TRIE - INSERT ALL WORDS
═══════════════════════════════════════════════

Insert "a":
  root → a (word = "a")

Insert "ap":
  root → a → p (word = "ap")

Insert "app":
  root → a → p → p (word = "app")

Insert "appl":
  root → a → p → p → l (word = "appl")

Insert "apple":
  root → a → p → p → l → e (word = "apple")

Insert "apply":
  root → a → p → p → l → y (word = "apply")

Insert "banana":
  root → b → a → n → a → n → a (word = "banana")

Final Trie:
                    root
                   /    \
                  a      b
                  |      |
                  p      a
                  |      |
                  p      n
                  |      |
                  l      a
                 / \     |
                e   y    n
                         |
                         a

Words marked at end nodes:
  "a" at node 'a' (depth 1)
  "ap" at node 'p' (depth 2)
  "app" at node 'p' (depth 3)
  "appl" at node 'l' (depth 4)
  "apple" at node 'e' (depth 5)
  "apply" at node 'y' (depth 5)
  "banana" at node 'a' (depth 6)

═══════════════════════════════════════════════

PHASE 2: DFS Search for Longest Valid Word

═══════════════════════════════════════════════
DFS EXPLORATION (Alphabetical Order)
═══════════════════════════════════════════════

Start at root:
  current = ""
  longest = ""

Explore child 'a':
  node = 'a', word = "a"
  word != null? YES ✓
  current = "a"
  longest = "a" (length 1)

  Explore children of 'a':

    Explore child 'p':
      node = 'p', word = "ap"
      word != null? YES ✓
      current = "ap"
      candidate so far = "ap" (length 2)

      Explore children of 'p':

        Explore child 'p':
          node = 'p', word = "app"
          word != null? YES ✓
          current = "app"
          candidate so far = "app" (length 3)

          Explore children of 'p':

            Explore child 'l':
              node = 'l', word = "appl"
              word != null? YES ✓
              current = "appl"
              candidate so far = "appl" (length 4)

              Explore children of 'l':

                Explore child 'e':
                  node = 'e', word = "apple"
                  word != null? YES ✓
                  current = "apple"
                  candidate = "apple" (length 5)
                  Has no children
                  Return "apple" to parent 'l'

                Explore child 'y':
                  node = 'y', word = "apply"
                  word != null? YES ✓
                  current = "apply"
                  candidate = "apply" (length 5)
                  Has no children
                  Return "apply" to parent 'l'

              Compare "apple" vs "apply":
                Both length 5
                "apple" < "apply" lexicographically ✓
              Return "apple" to parent 'p'

            Return "apple" to parent 'p'

          Return "apple" to parent 'p'

        Return "apple" to parent 'a'

      Return "apple" to parent 'a'

    Return "apple" to parent root

Explore child 'b':
  node = 'b', word = null
  word == null? YES ✗

  STOP! Cannot explore this branch!
  Why? No complete word at 'b'
  This means "b" is not in dictionary
  So "banana" cannot be built step-by-step!

  Skip this entire branch!

Final result from root: "apple"

═══════════════════════════════════════════════
RESULT: "apple"
═══════════════════════════════════════════════

Why "banana" is Skipped:

Detailed check for "banana":

Path in Trie: b → a → n → a → n → a

Check node 'b':
  word = null (no word "b" in dictionary) ✗

DFS Rule: Only continue if node.word != null

Since 'b' has word = null:
  → Cannot explore further!
  → "banana" is automatically excluded!

This is the POWER of Trie + DFS:
  - Automatically validates prefix chain
  - No need to manually check each prefix
  - Invalid words are naturally filtered out! 🎯

Key Observations:

1. DFS explores in alphabetical order
   - Children visited from 'a' to 'z'
   - Ensures lexicographical preference

2. Only valid chains explored
   - node.word != null check is CRITICAL
   - Ensures all prefixes exist
   - "banana" skipped because "b" not in dict

3. Longest word tracked during DFS
   - Each valid word compared
   - Length first, then lexicographical
   - "apple" wins over "apply"

4. No substring creation needed
   - Words stored in Trie nodes
   - Efficient memory usage
   - O(n * k) total time

5. Natural prefix validation
   - Trie structure enforces it
   - Invalid chains cannot be traversed
   - Elegant solution! ✨

---

📊 Complexity Analysis

Approach 3: Trie + DFS (Optimal)

Time Complexity:

n = number of words
k = average word length

Build Trie:
  - Insert n words
  - Each word: O(k) to traverse
  - Total: O(n * k)

DFS Search:
  - Visit each node in Trie at most once
  - Total nodes: O(n * k) worst case
  - At each node: O(1) operations
  - Total: O(n * k)

Overall: O(n * k) + O(n * k) = O(n * k) ✨

Compare with brute force:
  - Check all prefixes for each word: O(n * k²)

Trie approach is faster! 🚀

Space Complexity:

Trie space:
  - Worst case: all words have unique characters
  - O(n * k) nodes

DFS recursion stack:
  - Maximum depth = longest word length
  - O(k) stack space

Overall: O(n * k) 📦

Space is justified by:
  - Optimal time complexity
  - Natural prefix sharing
  - No substring creation
  - Elegant solution structure

---

🎯 Pattern Recognition

Trie Pattern #4: Prefix Chain Validation

┌──────────────────────────────────────────────────────┐
│    PATTERN 4: PREFIX CHAIN VALIDATION (BUILD-UP)     │
├──────────────────────────────────────────────────────┤
│ Use Case: Words built incrementally                  │
│ Problems: 165 (Longest Word in Dictionary)           │
│                                                       │
│ Key Property:                                         │
│   ALL intermediate prefixes must exist               │
│   Must be buildable one character at a time          │
│                                                       │
│ Algorithm:                                            │
│   1. Build Trie with all words                       │
│   2. DFS with constraint:                            │
│      - Only explore nodes with word != null          │
│      - This ensures unbroken prefix chain            │
│   3. Track longest valid word                        │
│                                                       │
│ Example:                                              │
│   Valid: "apple" if "a","ap","app","appl" exist      │
│   Invalid: "apple" if "ap" missing                   │
│                                                       │
│ DFS Template:                                         │
│   if (child != null && child.word != null) {         │
│       // Only explore valid chains                   │
│       dfs(child);                                     │
│   }                                                   │
└──────────────────────────────────────────────────────┘

This is DIFFERENT from other Trie patterns! 🔑

Compare All Trie Patterns:

┌──────────────────────────────────────────────────────┐
│         Pattern 1: EXACT WORD SEARCH                 │
│ Problems: 161                                         │
│ Check: isEndOfWord at END only                       │
│ Use: Dictionary lookup                               │
└──────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────┐
│         Pattern 2: WILDCARD SEARCH                   │
│ Problems: 162                                         │
│ Check: Backtracking with wildcards                   │
│ Use: Pattern matching                                │
└──────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────┐
│         Pattern 3: PREFIX SEARCH (SHORTEST)          │
│ Problems: 164                                         │
│ Check: isEndOfWord at EACH step, stop at first       │
│ Use: Root replacement                                │
└──────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────┐
│         Pattern 4: PREFIX CHAIN VALIDATION           │
│ Problems: 165                                         │
│ Check: ALL ancestors must have word != null          │
│ Use: Incremental building                            │
└──────────────────────────────────────────────────────┘

Each pattern solves a DIFFERENT class of problems! 🎯

Related Problems:

1. Implement Trie (208)
   Pattern: Basic structure

2. Design Add and Search Words (211)
   Pattern: Wildcard search

3. Replace Words (648)
   Pattern: Prefix search (shortest)

4. Longest Word in Dictionary (720) - This problem!
   Pattern: Prefix chain validation

5. Word Search II (212)
   Pattern: Trie + board backtracking

6. Implement Magic Dictionary (676)
   Pattern: One-character-off search

All use Trie but with different constraints! 🎯

---

🔍 Common Mistakes

❌ Mistake 1: Not checking prefix chain

// WRONG! - Doesn't validate all prefixes exist
private String dfs(TrieNode node) {
    String longest = node.word == null ? "" : node.word;

    // Explores all children without checking if they're complete words!
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {  // Missing validation!
            String candidate = dfs(node.children[i]);
            if (candidate.length() > longest.length()) {
                longest = candidate;
            }
        }
    }
    return longest;
}

// CORRECT! ✓ - Validates prefix chain
private String dfs(TrieNode node) {
    String longest = node.word == null ? "" : node.word;

    for (int i = 0; i < 26; i++) {
        TrieNode child = node.children[i];
        // CRITICAL: Check if child represents a complete word!
        if (child != null && child.word != null) {
            String candidate = dfs(child);
            if (candidate.length() > longest.length() ||
                (candidate.length() == longest.length() && 
                 candidate.compareTo(longest) < 0)) {
                longest = candidate;
            }
        }
    }
    return longest;
}

❌ Mistake 2: Wrong lexicographical comparison

// WRONG! - Only checks length
if (candidate.length() > longest.length()) {
    longest = candidate;
}

// CORRECT! ✓ - Checks length first, then lexicographical
if (candidate.length() > longest.length() ||
    (candidate.length() == longest.length() && 
     candidate.compareTo(longest) < 0)) {
    longest = candidate;
}

// Why this matters:
// For "apple" and "apply" (both length 5):
// "apple" < "apply" → should choose "apple"

❌ Mistake 3: Starting DFS from wrong place

// WRONG! - Starts from root's children
for (int i = 0; i < 26; i++) {
    if (root.children[i] != null) {
        result = dfs(root.children[i]);
    }
}

// CORRECT! ✓ - Starts from root itself
result = dfs(root);

// Why: Root itself might not represent a word,
// but its children do, and we want to find the longest
// chain starting from the beginning.

❌ Mistake 4: Not storing word at end nodes

// WRONG! - Only uses isEndOfWord flag
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

// Then during DFS, trying to reconstruct word - inefficient!

// CORRECT! ✓ - Store complete word
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;  // Store complete word here!
}

// Much cleaner and more efficient!
node.word = word;  // During insert
return node.word;  // During DFS

---

📝 Quick Revision Notes

🎯 Core Concept

Longest Word in Dictionary requires finding the longest word where ALL prefixes exist. Use Trie + DFS where we only explore children that represent complete words (child.word != null). This ensures unbroken prefix chain. Build Trie O(nk), DFS O(nk). Visit children in order (a-z) for natural lexicographical preference. Store complete word at end nodes for efficiency.

⚡ Quick Implementation

class TrieNode {
  TrieNode[] children;
  boolean isEnd;
  String word; // saves the word when isEnd is true. Just for comfort and for some use case problem like // Longest word in dict

  public TrieNode() {
    // Just space allocated. All are NULLs.
    // For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
    // Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
    // Check insert method. Only when character comes, we go and initialize that element in the array.
    // For binary numbers, you do need 26 (as its just 0 or 1). Also, isEnd is not required. 
    // But lets use the same for all problems to have it generic.
    this.children = new TrieNode[26];
    this.isEnd = false;
    this.word = null;
  }  
}

public class Solution {
  TrieNode root;

  public String longestWord(String[] words) {
    root = new TrieNode(); 

    // Build Trie (same as before. Only save word at the end node)
    for(String word : words) {
      insert(word);
    }

    return dfs(root);
  }

  private String dfs(TrieNode curr) {
    String res = "";
    // check if the current node itself is end of a word.
    if(curr != null && curr.word != null) {
      res = curr.word;
    }

    // Assume you came as root node here.
    for(int i = 0; i < 26; i++) {
      TrieNode child = curr.children[i];
      // if no word starts at this character like in dict: ["apple", "banana"], you can skip for child 'c'
      if(child == null) {
        continue;
      }

      // if there is no word created at this node, still you ignore it. 
      // For example, in ["apple", "a", "app", "appl"], there is no "ap". So, we should drop and cannot continue.
      if(child.word == null) {
        continue;
      }

      // Now, there exists a word, we have to continue. 
      // For example, in ["apple", "a", "ap", "app", "appl"], we have to continue till apple and compare with above "res".
      // Now, proceed with this child.
      String word = dfs(child);

      // We got a word from children which can be 1 char or 2 char or 5 char.
      if(word != null) {
        // compare lengths. If greater, update result or else if equal, update result based upon lexographic comparison.
        if(word.length() > res.length() || (word.length() == res.length() && word.compareTo(res) < 0)) {
          res = word;
        }
      }
    }

    return res;
  }

  private void insert(String word) {
    TrieNode curr = root;
    for(char ch : word.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        curr.children[index] = new TrieNode();
      }

      curr = curr.children[index];
    }

    curr.isEnd = true; // Not required actually for this problem as we are storing word itself in other field.
    curr.word = word; // CHANGE / EXTRA
  }

  public static void main(String[] args) {
        Solution s = new Solution();
    System.out.println(s.longestWord(new String[] {"w","wo","wor","worl","world"})); // "world"
    System.out.println(s.longestWord(new String[] {"a","banana","app","appl","ap","apply","apple"})); // "apple"
    }
}

🔑 Key Insights

The Critical Check:

Why child.word != null is essential:

WITHOUT this check:
  - Explores paths even if intermediate words missing
  - "banana" would be considered valid
  - Even though "b" is not in dictionary!

WITH this check:
  - Only explores if each step is a complete word
  - "banana" rejected because "b" not in dict
  - Ensures ALL prefixes exist! 🎯

Lexicographical Order:

DFS visits children in order (i = 0 to 25):
  - 'a' before 'b' before 'c', etc.
  - When lengths tie, earlier alphabet wins
  - Natural sorting without extra effort!

Example: "apple" vs "apply"
  Both length 5
  DFS finds "apple" first (e comes before y)
  "apple" < "apply" → "apple" chosen ✓

Why Store Complete Word:

Instead of:
  - Reconstructing word during DFS
  - Passing StringBuilder
  - Character-by-character building

We store:
  node.word = "apple"  // At end of insert
  return node.word      // During DFS

Benefits:
  - Cleaner code
  - More efficient
  - No string concatenation overhead

🎪 Memory Hooks

"Only explore if ALL ancestors have word != null!"
"DFS in alphabetical order = natural lexicographical!"
"Store complete word at end nodes!"
"Length first, then lexicographical!" 🔥

⚠️ Don't Forget

• Check child.word != null before exploring (CRITICAL!)
• Compare length first, THEN lexicographical order
• Visit children in order (0 to 25) for natural sorting
• Store complete word at end nodes (not just boolean flag)
• Start DFS from root (not root's children)
• Handle empty result case (return "")

---

🎉 Congratulations!

You've mastered Trie Prefix Chain Validation!

What You Learned:

✅ Prefix chain validation - ensure ALL prefixes exist
✅ DFS with constraints - only explore valid chains
✅ Natural lexicographical order - visit children a to z
✅ Word storage optimization - store complete words
✅ O(n*k) complexity - optimal linear solution
✅ New Trie pattern - incremental building verification

The Four Trie Patterns:

Pattern 1 (161): EXACT WORD SEARCH
  Check at end only

Pattern 2 (162): WILDCARD SEARCH
  Backtracking with wildcards

Pattern 3 (164): PREFIX SEARCH (SHORTEST)
  Check at each step, stop first

Pattern 4 (165): PREFIX CHAIN VALIDATION
  Check all ancestors have word != null

Four distinct patterns for four distinct problems! 🎯

Interview Mastery:

Interviewer: "Find longest word buildable step-by-step"

Your response:
  "This is a prefix chain validation problem!

   Key insight:
   - Word is valid only if ALL prefixes exist
   - 'apple' needs 'a', 'ap', 'app', 'appl'
   - Missing any prefix → invalid!

   Approach:
   1. Build Trie with all words
   2. Store complete word at end nodes (optimization)
   3. DFS with special constraint:
      - Only explore if child.word != null
      - This validates prefix chain!
   4. Visit children in order (a-z)
      - Natural lexicographical sorting
   5. Track longest valid word found

   Why Trie wins:
   - Natural prefix structure
   - O(n*k) vs O(n*k²) for brute force
   - Automatic prefix chain validation
   - No substring creation needed

   The key check:
   - if (child != null && child.word != null)
   - Ensures unbroken chain of complete words

   Complexity:
   - Time: O(n*k) - linear!
   - Space: O(n*k) for Trie

   This pattern is unique - validates incremental building!"

Shows deep understanding! 💯

Your Trie Mastery Journey:

Problem 161: Basic Trie ✓
  - Insert, Search, StartsWith
  - Foundation

Problem 162: Wildcard Trie ✓
  - Backtracking with '.'
  - Pattern matching

Problem 163: Binary Trie ✓
  - 2 children for XOR
  - Bit manipulation

Problem 164: Prefix Search Trie ✓
  - Check at each step
  - Shortest prefix

Problem 165: Chain Validation Trie ✓
  - All ancestors must be valid
  - Incremental building

You're now a Trie EXPERT! 🏆✨🎯

You've mastered 5 different Trie patterns! Keep crushing it! 🚀