Frontend School

Find Shortest Unique Prefixes

DSA
medium

Find Shortest Unique Prefixes

Medium
Trie
String
Data Structures
Prefix Sum

Overview

Atlassian products like Jira and Confluence often manage vast amounts of user-generated content, project names, and file paths. Efficiently identifying and disambiguating these entities is crucial for search, auto-completion, and user experience. This problem models a scenario where we need to generate the shortest possible unique identifiers for a given set of words or names.

What you need to do / Task

Implement the function findShortestUniquePrefixes that takes a list of strings (words) and returns a new list. For each word in the input list, the corresponding element in the output list should be its shortest unique prefix.

A prefix P of a word W is considered "unique" if no other word W' in the input list has P as its prefix. If a word itself is the shortest unique prefix, then the word itself should be returned.

Input & output

Function Signature:

function findShortestUniquePrefixes(words: string[]): string[]

Parameters:

  • words: An array of strings. Each string represents a word for which a shortest unique prefix needs to be found. The order of words in the input array should be preserved in the output.

Return Value:

  • An array of strings, where output[i] is the shortest unique prefix for words[i]. The length and order of the output array must match the input array.

Clarifications

  • Empty input: If the words array is empty, return an empty array.
  • Duplicate words: If the input words array contains duplicate strings, each instance should be treated as a distinct word, and its shortest unique prefix should be determined accordingly. For example, if words = ["apple", "apple"], the output would be ["apple", "apple"] because 'a', 'ap', etc. are not unique to a single instance of "apple".
  • Single word input: If the input array contains only one word, its shortest unique prefix will be its first character (assuming the word is not empty), as it's trivially unique.
  • Character set: All words will consist of lowercase English letters.

Examples

1

Example 1

Input:

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

Output:

["apple", "apr", "b", "apply"]

Note:

For "apple", "appl" is also a prefix of "apply", so "apple" itself is the shortest unique prefix. For "apricot", "apr" is unique. For "banana", "b" is unique. For "apply", "appl" is shared with "apple", so "apply" itself is the shortest unique prefix.

2

Example 2

Input:

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

Output:

["z", "dog", "du", "dov"]

Note:

For "zebra", 'z' is unique. For "dog", 'd' is shared, 'do' is shared, but 'dog' is unique. For "duck", 'd' is shared, 'du' is unique. For "dove", 'd' is shared, 'do' is shared, but 'dov' is unique.

3

Example 3

Input:

words = ["atlassian", "atlas"]

Output:

["atlassian", "atlas"]

Note:

For "atlassian", "atlas" is a prefix of itself and "atlas", so "atlassian" is its shortest unique prefix. For "atlas", as it's a prefix of "atlassian", "atlas" itself is its shortest unique prefix.

4

Example 4

Input:

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

Output:

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

Note:

Each word is unique from its first character.

Constraints

Constraints & assumptions

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

Out of scope

  • Handling words with non-alphabetic characters or mixed case.
  • Optimizing for extreme memory constraints beyond a standard Trie implementation.

What interviewers evaluate

  • Correctness: The solution correctly identifies the shortest unique prefix for all words, handling edge cases like duplicate words or words that are prefixes of others.
  • Efficiency: The solution demonstrates optimal time and space complexity for Trie construction and prefix lookup.
  • Code Quality: The code is well-structured, readable, and follows good software engineering practices.
  • Problem-Solving: The candidate articulates their thought process, considers different approaches, and justifies their chosen solution.

Loading editor...