Shortest Uncommon Substring in an Array
You are given an array arr of size n consisting of non-empty strings.
Find a string array answer of size n such that:
answer[i]is the shortest substring ofarr[i]that does not occur as a substring in any other string inarr.- If multiple such substrings exist,
answer[i]should be the lexicographically smallest. - If no such substring exists,
answer[i]should be an empty string.
Return the array answer.
Example 1
Input
arr = ["cab","ad","bad","c"]Output
["ab","","ba",""]For "cab", both "ca" and "ab" are shortest unique substrings and "ab" is lexicographically smaller; "ad" and "c" have none, and "bad" has "ba".
Example 2
Input
arr = ["abc","bcd","abcd"]Output
["","","abcd"]The strings "abc" and "bcd" have no substring absent from the other strings, while "abcd" has shortest uncommon substring "abcd".
Constraints
- n == arr.length
- 2 <= n <= 100
- 1 <= arr[i].length <= 20
- arr[i] consists only of lowercase English letters.