A console keeps a set of known command words. A command can be typed 'one character at a time' if every one of its non-empty proper prefixes is also a known command. (A single-letter command is always considered buildable, since it has no proper prefixes to require.)
Find the longest command that can be built one character at a time. If several commands of that maximum length qualify, choose the lexicographically smallest. If no command qualifies, print NONE.
The list may contain duplicates; treat it as a set. All commands consist of lowercase English letters only.
Line 1: an integer n.
Line 2: n space-separated command words.
A single line: the chosen command, or NONE.
Example 1
Input
5 a ap app appl apple
Expected
apple
Explanation
Every proper prefix of apple (a, ap, app, appl) is present, so apple can be built one character at a time and is the longest such word.
Example 2
Input
4 zz z aa a
Expected
aa
Explanation
Both aa (needs a) and zz (needs z) are buildable and have length 2; the lexicographically smaller one, aa, is chosen.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →