# 3076. Shortest Uncommon Substring in an Array

## Description

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.length
• 2 <= n <= 100
• 1 <= arr[i].length <= 20
• arr[i] consists only of lowercase English letters.

## Solutions

### Solution 1: Enumeration

Given the small data scale, we can directly enumerate all substrings of each string and then determine whether it is a substring of other strings.

Specifically, we first enumerate each string arr[i], then enumerate the length $j$ of each substring from small to large, and then enumerate the starting position $l$ of each substring. We can get the current substring as sub = arr[i][l:l+j]. Then we determine whether sub is a substring of other strings. If it is, we skip the current substring; otherwise, we update the answer.

The time complexity is $O(n^2 \times m^4)$, and the space complexity is $O(m)$. Where $n$ is the length of the string array arr, and $m$ is the maximum length of the string. In this problem, $m \le 20$.

• class Solution {
public String[] shortestSubstrings(String[] arr) {
int n = arr.length;
String[] ans = new String[n];
Arrays.fill(ans, "");
for (int i = 0; i < n; ++i) {
int m = arr[i].length();
for (int j = 1; j <= m && ans[i].isEmpty(); ++j) {
for (int l = 0; l <= m - j; ++l) {
String sub = arr[i].substring(l, l + j);
if (ans[i].isEmpty() || sub.compareTo(ans[i]) < 0) {
boolean ok = true;
for (int k = 0; k < n && ok; ++k) {
if (k != i && arr[k].contains(sub)) {
ok = false;
}
}
if (ok) {
ans[i] = sub;
}
}
}
}
}
return ans;
}
}

• class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
int n = arr.size();
vector<string> ans(n);
for (int i = 0; i < n; ++i) {
int m = arr[i].size();
for (int j = 1; j <= m && ans[i].empty(); ++j) {
for (int l = 0; l <= m - j; ++l) {
string sub = arr[i].substr(l, j);
if (ans[i].empty() || sub < ans[i]) {
bool ok = true;
for (int k = 0; k < n && ok; ++k) {
if (k != i && arr[k].find(sub) != string::npos) {
ok = false;
}
}
if (ok) {
ans[i] = sub;
}
}
}
}
}
return ans;
}
};

• class Solution:
def shortestSubstrings(self, arr: List[str]) -> List[str]:
ans = [""] * len(arr)
for i, s in enumerate(arr):
m = len(s)
for j in range(1, m + 1):
for l in range(m - j + 1):
sub = s[l : l + j]
if not ans[i] or ans[i] > sub:
if all(k == i or sub not in t for k, t in enumerate(arr)):
ans[i] = sub
if ans[i]:
break
return ans


• func shortestSubstrings(arr []string) []string {
ans := make([]string, len(arr))
for i, s := range arr {
m := len(s)
for j := 1; j <= m && len(ans[i]) == 0; j++ {
for l := 0; l <= m-j; l++ {
sub := s[l : l+j]
if len(ans[i]) == 0 || ans[i] > sub {
ok := true
for k, t := range arr {
if k != i && strings.Contains(t, sub) {
ok = false
break
}
}
if ok {
ans[i] = sub
}
}
}
}
}
return ans
}

• function shortestSubstrings(arr: string[]): string[] {
const n: number = arr.length;
const ans: string[] = Array(n).fill('');
for (let i = 0; i < n; ++i) {
const m: number = arr[i].length;
for (let j = 1; j <= m && ans[i] === ''; ++j) {
for (let l = 0; l <= m - j; ++l) {
const sub: string = arr[i].slice(l, l + j);
if (ans[i] === '' || sub.localeCompare(ans[i]) < 0) {
let ok: boolean = true;
for (let k = 0; k < n && ok; ++k) {
if (k !== i && arr[k].includes(sub)) {
ok = false;
}
}
if (ok) {
ans[i] = sub;
}
}
}
}
}
return ans;
}