#3076
Shortest Uncommon Substring in an Array
specialist · 885 · lc medium +31 · verified · 50% accepted · 170 likes · top 38%
Description
Given a string array arr of n non-empty strings, build a result array answer where answer[i] is the shortest substring of arr[i] that does not appear in any other string in arr. Break length ties lexicographically. If no such substring exists, use an empty string. Return answer.
Example 1:
Input: arr = ["cab","ad","bad","c"]
Output: ["ab","","ba",""]
Explanation: We have the following:
- For the string "cab", the shortest substring that does not occur in any other string is either "ca" or "ab", we choose the lexicographically smaller substring, which is "ab".
- For the string "ad", there is no substring that does not occur in any other string.
- For the string "bad", the shortest substring that does not occur in any other string is "ba".
- For the string "c", there is no substring that does not occur in any other string.
Example 2:
Input: arr = ["abc","bcd","abcd"]
Output: ["","","abcd"]
Explanation: We have the following:
- For the string "abc", there is no substring that does not occur in any other string.
- For the string "bcd", there is no substring that does not occur in any other string.
- For the string "abcd", the shortest substring that does not occur in any other string is "abcd".
Code
1
2
3