You are given an array of strings, words. Your task is to find the longest string in words such that every prefix of this string is also present in words.

A prefix of a string is any leading substring. For example, the prefixes of "apple" are "a", "ap", "app", and "appl".

1. If multiple valid strings have the same maximum length, return the lexicographically smallest one.

2. If no such string exists, return an empty string "".

Constraints:

• $1 \leq$ words.length $\leq 10^3$

• $1 \leq$ words[i].length $\leq 10^3$

• $1 \leq$ sum(words[i].length) $\leq 10^3$

• words[i] consists only of lowercase English letters.

A trie (prefix tree) is a tree-based data structure that efficiently stores strings by sharing common prefixes. Each node in the trie represents a character, and the path from the root to any node corresponds to a word’s prefix.

This property makes tries especially useful for problems involving prefix relationships. In this problem, we use the trie to determine whether a word can be built one character at a time from other words in the list. Each word is inserted into the trie, and the end of every complete word is marked. Later, to validate any given word, we traverse it in the trie and confirm that each of its prefixes is also marked as a complete word. This structure enables efficient lookups and eliminates the need for repeated prefix searches through the original array.

The key idea is simple: A word is valid if, while traversing it in the trie, every node along its path represents a complete word.

Using this principle, the algorithm determines the longest word that can be built step by step from other words in the list. After inserting all words into the trie, each word is validated by ensuring that every prefix node corresponds to a complete word (is_end = True). Only those words meeting this condition are considered valid.

Among all valid words, the algorithm continuously tracks the longest one. If multiple words share the same length, it selects the lexicographically smallest (dictionary order) word. This ensures that the final result is the longest and lexicographically smallest word that can be formed by successively adding characters from existing words.

The steps of the algorithm are as follows:

1. Define a TrieNode class where each node represents a single character in a word. Each node contains:

   1. children: A dictionary mapping characters to their corresponding child nodes.

   2. is_end: A boolean flag (initialized as False) that indicates whether the current node marks the end of a complete word.

2. Initialize a Trie object with a root node. For every word in the input list:

   1. Start from the root node.

   2. For each character ch in the word:

      1. If ch is absent in the current node’s children, create a new TrieNode.

      2. Move to the child node corresponding to ch.

   3. After inserting the final character, mark the node’s is_end = True.

3. Define a method, is_valid_word(word), to determine whether a word can be formed by successively adding one character at a time from other valid words.

   1. Start from the root node and traverse each character in the word.

   2. Move to the corresponding child node for every character and check whether is_end is True.

   3. If any node’s is_end is False, it means that a prefix of the word is not a complete word, return False.

   4. Return True If all prefixes are valid (i.e., all nodes encountered have is_end = True).

4. Initialize an empty string, ans, to store the best result found so far. Iterate through all words in the list:

   1. If is_valid_word(word) returns True:

      1. If len(word) > len(ans), update ans = word.

      2. If len(word) == len(ans) and word < ans, update ans = word to ensure lexicographical order.

5. After checking all words, return ans as the longest valid word that can be built one character at a time from other words in the list.

Let’s look at the following illustration to get a better understanding of the solution: