Longest String with All Prefixes

Implement longestCompleteString

Given a list of words, find the longest one that's "complete" — every one of its prefixes, from length 1 up to its own full length, must also appear somewhere in the list. If several words tie for longest, return the alphabetically smallest of them; if not a single word qualifies, return the literal string "None". This is the same prefix-chain idea as building a word one character at a time: mark every trie node where some inserted word actually ends, then only ever walk into a child whose own node carries that mark. Any real node the walk reaches this way sits at the end of an unbroken chain of complete words. The one difference from a plain "longest buildable word" search is the empty starting point — the root itself is never a real candidate, so if the walk can't step into even a single child, nothing was complete and the answer falls back to "None" rather than an empty string.

Example 1:

Input: words = ["n","ni","nin","ninj","ninja","ninga"]

Output: "ninja"

Example 2:

Input: words = ["a","ab","abc"]

Output: "abc"

Example 3:

Input: words = ["cat","dog","elephant"]

Output: "None"

+ 10 hidden test cases run on Submit.

Constraints:

  • 0 ≤ words.length ≤ 1000
  • 1 ≤ words[i].length ≤ 30
  • words consists of lowercase English letters
  • words may contain duplicates

words =

["n", "ni", "nin", "ninj", "ninja", "ninga"]