Watch 10 video solutions for Shortest Uncommon Substring in an Array, a medium level problem involving Array, Hash Table, String. This walkthrough by Ashish Pratap Singh has 1,002,285 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 of arr[i] that does not occur as a substring in any other string in arr. If multiple such substrings exist, answer[i] should be the lexicographically smallest. And 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",""] 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".
Constraints:
n == arr.length2 <= n <= 1001 <= arr[i].length <= 20arr[i] consists only of lowercase English letters.