Frontend School

Shortest Unique Prefixes

DSA
medium

Shortest Unique Prefixes

Medium
String
Trie
prefix

Overview

At Shiprocket, optimizing logistics often involves efficient data structures for managing routes, package identifiers, or even product catalogs. Imagine a scenario where you have a large inventory of product SKUs or shipment IDs, and you need to quickly identify each item using the shortest possible identifier that uniquely distinguishes it from all other items. This problem challenges you to design a solution that generates the shortest unique prefix for every given word in a list, reflecting a real-world need for compact and unambiguous identification.

What you need to do / Task

You are tasked with implementing a function findShortestUniquePrefixes that takes an array of strings (words) and returns an array of strings, where each element is the shortest unique prefix for the corresponding word in the input array.

A "shortest unique prefix" for a word W is defined as the shortest possible prefix of W such that this prefix does not also serve as a prefix for any other word in the input list. If a word is unique by its first character, its shortest unique prefix is just that character.

Input & output

Input:

  • words: An array of strings (string[]). Each string consists of lowercase English letters.

Output:

  • An array of strings (string[]). The i-th element of the output array should be the shortest unique prefix for words[i]. The order of prefixes in the output array must match the order of words in the input array.

Clarifications

  • Empty input array? The input array words will not be empty.
  • Empty strings? Words in the input array will not be empty strings.
  • Duplicate words? The input array may contain duplicate words. If duplicates exist, they should each receive the same shortest unique prefix. For example, if ["apple", "apple", "banana"], both "apple" entries will have the same shortest unique prefix.
  • All words are unique? If all words are unique and no word is a prefix of another, then their first character might be their shortest unique prefix (e.g., ["a", "b", "c"] -> ["a", "b", "c"]). If words are ["apple", "banana"], then ["a", "b"]. If words are ["apple", "apricot"], then ["app", "apr"].

Examples

1

Example 1

Input:

words = ["zebra", "dog", "duck", "dove"]

Output:

["z","dog","duc","dov"]

Note:

For "zebra", 'z' is unique. For "dog", 'd' is not unique (duck, dove). 'do' is not unique (dove). 'dog' is unique. For "duck", 'd' is not unique, 'du' is not unique, 'duc' is unique. For "dove", 'd' is not unique, 'do' is not unique, 'dov' is unique.

2

Example 2

Input:

words = ["apple", "apply", "apricot", "banana"]

Output:

["appl","appl","apr","b"]

Note:

For "apple" and "apply", 'app' is shared. 'appl' differentiates them. For "apricot", 'ap' is shared with "apple"/"apply", 'apr' is unique. For "banana", 'b' is unique.

3

Example 3

Input:

words = ["a","b","c","apple","apply"]

Output:

["a","b","c","appl","appl"]

Note:

Single-character words are unique. For "apple" and "apply", 'appl' is the shortest unique prefix.

Constraints

Constraints & assumptions

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 100
  • words[i] consists only of lowercase English letters ('a'-'z').
  • The total number of characters across all words will not exceed 10^6.

Out of scope

  • Handling non-alphabetic characters or uppercase letters. Assume inputs are always lowercase English letters.
  • Optimizing for memory beyond standard Trie implementations. Focus on time complexity.

What interviewers evaluate

  • Correctness of logic: Does the solution accurately identify the shortest unique prefix for all words?
  • Trie implementation: Proper construction and traversal of the Trie data structure.
  • Time and space complexity: Efficiency of the algorithm, especially for large inputs.
  • Code structure and readability: Clean, well-organized, and easy-to-understand code.

Loading editor...