Buildable name: hints, no solution
Medium · Tries
A username picker only accepts a name that can be built one letter at a time: every non-empty prefix of it, including the name itself, must also appear in a list of reserved names. Given that list, which may contain repeats and is in no particular order, return the longest buildable name that appears in it.
If several buildable names have the same length, return the alphabetically smallest of them. If no name in the list is buildable, return the empty string. Names use lowercase letters only.
Examples
- Input
- names = ["w", "wo", "wor", "worl", "world", "word", "wr"]
- Output
- "world"
- Note
- Each of w, wo, wor, worl and world is in the list, so world is buildable and is the longest.
- Input
- names = ["a", "ab", "ac", "b"]
- Output
- "ab"
- Note
- ab and ac are both buildable with length 2, and ab comes first alphabetically.
- Input
- names = ["banana", "ban", "ba"]
- Output
- ""
- Note
- No name starts from a one-letter name that is in the list, so nothing can be built.
Constraints
- 1 <= names.length <= 90000
- Each name has 1 to 30 lowercase letters
- The list may contain repeated names
Hint 1: a nudge
What has to be true of every shorter start of a name before that name can be accepted? Which names can you decide first, and which depend on others?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.