Standard Bar Tries · Problems O(total characters) · O(total characters)
A domain registrar audits customer names: a name is trustworthy only if every one of its growing prefixes — starting from the first letter — is itself a registered name. Among the trustworthy names the registrar awards the longest one, breaking length ties by alphabetical order. If no name qualifies, the audit returns "None".
Input: An integer n and an array a of n lowercase strings.
Output: Return the longest string whose every prefix is present in a (lexicographically smallest on ties), or "None" when no string qualifies.
1 <= n <= 10^51 <= len(a[i]) <= 10^5 (total characters bounded)strings use lowercase English lettersInput: {"n":4,"a":["ab","abc","a","bp"]}
Output: "abc"
"a" and "ab" are registered, so "abc" is complete; "bp" fails at prefix "b".
Input: {"n":5,"a":["n","ni","nin","ninj","ninja"]}
Output: "ninja"
Every rung of the ladder n, ni, nin, ninj, ninja is present.