Track Search Badges
Shortest distinguishing prefix for each string in an array
A music streaming app assigns a search badge to each entry in its track catalog. The catalog is given as an array titles of lowercase title codes.
A badge for entry i must be a nonempty prefix of titles[i] that is not a prefix of any other catalog entry. Return the shortest such badge for every entry, in the same order as titles.
If no prefix can distinguish an entry, return an empty string "" for that entry. Entries are considered separate even when their title codes are identical, so duplicate titles cannot receive distinguishing badges.
Matching uses prefixes only: a title appearing in the middle of another title does not matter.
Examples
Example 1
Input: titles = ["cello","celesta","drum"] Output: ["cell","cele","d"]
The first two titles share their opening letters but eventually diverge. The third title can be distinguished immediately because it starts with a different letter.
Example 2
Input: titles = ["echo","echoes"] Output: ["","echoe"]
The shorter title is a prefix of the longer title, so it cannot have a distinguishing badge. The longer title can be distinguished after extending beyond the shorter one.
Example 3
Input: titles = ["pulse","pulse","harp"] Output: ["","","h"]
The repeated title codes represent separate entries and cannot distinguish themselves from each other. The remaining title can receive a badge.
Constraints
- 0 <= titles.length <= 2000
- 1 <= titles[i].length <= 40
- Each title contains only lowercase English letters.
- The sum of all title lengths is at most 12000.
An empty catalog produces an empty result list. A full title is an allowed badge if it distinguishes its entry. The intended solution takes O(S) time and O(S) space, where S is the sum of the title lengths.
Hints
Show hint 1Hint 1
Insert every title into a trie, recording how many catalog entries pass through each node.
Show hint 2Hint 2
For each title, find the first node on its path that is visited by exactly one entry.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you update badges if catalog entries could be inserted and removed?
- How would the result change if identical title codes were treated as one entry rather than separate entries?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem