Shortest unique prefix: hints, no solution
Medium · Tries
A catalogue app labels each product with the shortest prefix of its name that no other product name starts with. All names are distinct lowercase words.
For example, if the catalogue holds apple and apply, the label for apple must be the whole word, because every shorter prefix is also the start of apply. If even the whole name is the start of another name, as bat is the start of batch, the label is simply the whole name.
For every name, in the input order, return its label.
Examples
- Input
- names = ["apple", "apply", "apt", "bat", "batch"]
- Output
- ["apple", "apply", "apt", "bat", "batc"]
- Note
- apple and apply share appl, so both need five letters; apt is settled by its third letter; bat is a prefix of batch so it stays whole, and batch needs batc.
- Input
- names = ["zebra"]
- Output
- ["z"]
- Note
- A lone name is identified by its first letter.
- Input
- names = ["ab", "abc", "abd"]
- Output
- ["ab", "abc", "abd"]
- Note
- ab is a prefix of both abc and abd, so all three names stay whole.
Constraints
- 1 <= names.length <= 24000
- Each name has 1 to 12 lowercase letters
- All names are distinct
Hint 1: a nudge
For one name, how would you decide whether a given prefix of it is shared with some other name? Which prefixes do you have to test, and in what order?
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.