Shortest Uncommon Substring in an Array

You are given an array of strings arr.

For each string arr[i], you must find its shortest distinguishing substring: the shortest non-empty substring of arr[i] that does not appear as a substring of any other string in arr (that is, of arr[j] for every j != i). Occurrences within arr[i] itself do not disqualify a substring — only appearances inside the other strings matter.

Among all substrings of arr[i] that satisfy this uniqueness condition, pick the shortest one. If several substrings share that minimal length, pick the lexicographically smallest among them. If no substring of arr[i] is unique to it (every possible substring also occurs in some other string), the answer for that index is the empty string "".

Return an array answer where answer[i] is the shortest distinguishing substring for arr[i], following the rules above.

Examples

Example 1:

Input: arr = ["cab", "ad", "bad"]

Output: ["c","","ba"]

Explanation:

• "cab" contains letter c, which never appears in "ad" or "bad", so the shortest distinguishing substring is "c".
• Every substring of "ad" (a, d, ad) also appears inside "bad", so no distinguishing substring exists and the answer is "".
• For "bad", single letters b, a, d all appear in "cab" or "ad", but "ba" appears in neither of the other strings, giving "ba".

Example 2:

Input: arr = ["aaa", "aa", "a"]

Output: ["aaa","",""]

Explanation:

• Substrings of "aaa" are a, aa, aaa; both a and aa occur inside "aa" or "a", but aaa does not, so the answer is "aaa".
• All substrings of "aa" (a, aa) occur inside "aaa", so there is no distinguishing substring.
• The only substring of "a" is a, which also occurs in "aaa" and "aa", so the answer is "".

Example 3:

Input: arr = ["xy", "yz", "zx"]

Output: ["xy","yz","zx"]

Explanation:

Each two-letter string uses a letter pair that never occurs together in either of the other two strings, so each whole string is already its own shortest distinguishing substring.

Constraints

• 2 <= arr.length <= 100
• 1 <= arr[i].length <= 20
• arr[i] consists of lowercase English letters only.