Problem

Submissions

Hints & solutions

Discuss

Shortest Unique Prefix

Moderate

0/80

Average time to solve is 15m

Contributed by

16 upvotes

Asked in companies

Problem statement

You are given an array containing ‘N’ words. For each word, you need to find its shortest prefix which can uniquely identify it. For example “abcd” and “abdc” both have the prefix “ab” in common so we can’t uniquely find a word using the prefix “ab”. To uniquely identify both the words we need the prefix “abc” from “abcd” and “abd” from “abdc”.

Note:

You can assume that the words are unique. It means that it is always possible to find a unique prefix for each word.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines describe the ‘T’ test cases.

The first line of each test case contains single positive integers ‘N’ denoting the number of words.
The next ‘N’ lines contain a string of lower case characters.

Output Format:

The output of each test case should contain 'N' lines, in the ith line you need to print the shortest unique prefix for ith word.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4  

Where ‘T’ is the number of test cases, ‘N’ is the number of words and, the sum of the lengths of all the words in a test case is less than 10^4.

Time Limit: 1 sec

Sample Input 1:

2
2
abcd
acdb
3
many
mango
mad

Sample Output 1:

ab
ac
many
mang
mad

Explanation for sample input 1:

Test case 1:
The string “abcd” and “acbd” have a common prefix “a” which can’t be used as a unique prefix so to make a unique prefix we will add one more character to “a” from each word. The “ab” for “abcd” and prefix “ac” for “acbd” is now the shortest and unique prefix.


Test case 2:
For string “many” the prefix “m” and “ma” is common in“mango” and “mad”. Similarly “man” is again common in “mango”. “Many” itself will be the unique shortest prefix.

For string “mango” we have the string ”many” such that “man” is common in both of them so for “mango” the prefix “mang” will the unique shorted prefix.

For string “mad” we have strings “many” and “mango” such that   “ma” is common in all of them. “Mad” itself will be a unique shortest prefix.

Sample Input 2:

2
3
sample
same
sort
2
quick
merge

Sample Output 2:

samp
same
so
q
m

Hint 1

Hint 2

Hint 3

Try all prefixes for each word

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute force

For each word, we will try each prefix one by one to check if this prefix can be the shortest unique prefix or not.
We will check the prefixes of length shortest to longest and for each prefix, we will find if this is already a prefix of some word or not. If this prefix is not a prefix of some other word then it is the unique prefix for our current word. Also, it will be the shortest prefix because we are checking the prefixes from length shortest to longest.
We will store each prefix of the word in an array and return it as the answer.

Time Complexity

O(S^2), where ‘S’ is the sum of the length of all the strings

In the worst case, we can have ‘S’ prefix possible and for each of the prefixes we will be comparing it will each character present in the input so total complexity will be O(S^2).

Space Complexity

O(1).

The output array does not count as extra space for the purpose of space complexity analysis. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Shortest Unique Prefix

Console