# Shortest Uncommon Substring in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-uncommon-substring-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/shortest-uncommon-substring-in-an-array
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Affirm](https://scaleengineer.com/companies/affirm), [Moveworks](https://scaleengineer.com/companies/moveworks)
---
## Problem
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.

# Approaches
## Brute-Force with Per-String Substring Set
This approach iterates through each string in the input array. For each string `arr[i]`, it first builds a set of all substrings from all *other* strings in the array. Then, it generates all substrings of `arr[i]`, ordered by length, and checks if they exist in the pre-computed set of "other" substrings. The first one it finds that is not in the set is the shortest uncommon substring. If multiple exist of the same shortest length, they are sorted to find the lexicographically smallest.
**Time:** O(n^2 * m^3). For each of the `n` strings, we build a set of substrings from `n-1` other strings. Building this set takes `O(n * m^3)` time. Then, we check `O(m^2)` substrings of the current string against this set, which takes `O(m^3)`. The total time is `O(n * (n*m^3 + m^3)) = O(n^2 * m^3)`. · **Space:** O(n * m^3), where `n` is the number of strings and `m` is their maximum length. The `otherSubstrings` set can store up to `O(n * m^2)` substrings, each of length up to `m`, leading to `O(n * m^3)` space in the worst case.
**Pros:** Relatively simple to understand and implement.
**Cons:** Highly inefficient due to re-computing the set of "other" substrings for each string in the input array.; The time and space complexity are high, making it unsuitable for larger constraints.
### Explanation
The main idea is to solve the problem for each string `arr[i]` independently. For a given `arr[i]`, we need to compare its substrings against the substrings of all `arr[j]` where `j != i`. To make this comparison efficient, we first gather all substrings from `arr[j]` (for all `j != i`) into a `HashSet` for quick lookups. This set, let's call it `otherSubstrings`, will contain every possible substring from the other words.

After building this set, we iterate through all possible substrings of `arr[i]`, starting from length 1 up to `arr[i].length()`. For each length, we generate all substrings of `arr[i]` of that length. For each generated substring, we check if it's present in `otherSubstrings`. If it's not present, it's an "uncommon" substring. We collect all such uncommon substrings for the current length.

If we find any uncommon substrings, we don't need to check longer lengths. We sort the collected candidates lexicographically and pick the first one as the answer for `arr[i]`. We then move on to the next string in the input array. If we iterate through all possible lengths for `arr[i]` and find no uncommon substrings, the answer for it is an empty string. This entire process is repeated for every string in the input array.

```java
import java.util.*;

class Solution {
    public String[] shortestUncommonSubstringInArray(String[] arr) {
        int n = arr.length;
        String[] answer = new String[n];

        for (int i = 0; i < n; i++) {
            // Step 1: Build a set of substrings from all other strings
            Set<String> otherSubstrings = new HashSet<>();
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < arr[j].length(); k++) {
                    for (int l = k + 1; l <= arr[j].length(); l++) {
                        otherSubstrings.add(arr[j].substring(k, l));
                    }
                }
            }

            // Step 2: Find the shortest uncommon substring for arr[i]
            String shortestUncommon = "";
            for (int len = 1; len <= arr[i].length(); len++) {
                List<String> candidates = new ArrayList<>();
                for (int k = 0; k <= arr[i].length() - len; k++) {
                    String sub = arr[i].substring(k, k + len);
                    if (!otherSubstrings.contains(sub)) {
                        candidates.add(sub);
                    }
                }
                if (!candidates.isEmpty()) {
                    Collections.sort(candidates);
                    shortestUncommon = candidates.get(0);
                    break;
                }
            }
            answer[i] = shortestUncommon;
        }
        return answer;
    }
}
```
### Algorithm
- 1. Initialize an `answer` array of size `n`.
- 2. For each string `arr[i]` from `i = 0` to `n-1`:
    - a. Create a `HashSet<String>` called `otherSubstrings`.
    - b. For each other string `arr[j]` where `j != i`:
        - i. Generate all substrings of `arr[j]`.
        - ii. Add each substring to `otherSubstrings`.
    - c. Initialize `foundAnswer = ""`.
    - d. For `len` from 1 to `arr[i].length()`:
        - i. Create a `List<String>` called `candidates`.
        - ii. For `start` from 0 to `arr[i].length() - len`:
            - 1. Get `sub = arr[i].substring(start, start + len)`.
            - 2. If `otherSubstrings` does not contain `sub`, add `sub` to `candidates`.
        - iii. If `candidates` is not empty:
            - 1. Sort `candidates` lexicographically.
            - 2. Set `foundAnswer = candidates.get(0)`.
            - 3. Break from the `len` loop.
    - e. Set `answer[i] = foundAnswer`.
- 3. Return `answer`.

## Pre-computation with Global Substring Map
This approach improves upon the brute-force method by avoiding redundant computations. It first processes all strings to build a global map. This map stores every unique substring found across all strings as keys. The value for each key is a set of indices of the strings in which that substring appears. After this pre-computation step, it iterates through each string `arr[i]`, generates its substrings by increasing length, and uses the map to quickly check if a substring is unique to `arr[i]`.
**Time:** O(n * m^3). Populating the map takes `O(n * m^3)` because we iterate through `n` strings, each having `O(m^2)` substrings of average length `O(m)`. Finding the answers also takes `O(n * m^3)`. The total time is dominated by these two phases. · **Space:** O(n * m^3). The map can store up to `O(n * m^2)` unique substrings. In the worst case, each substring has length `O(m)`, leading to `O(n * m^3)` space for the keys.
**Pros:** More efficient than the first approach by avoiding re-computation.; The logic is separated into a clean pre-computation phase and a solving phase.
**Cons:** The space complexity can be high if there are many long, unique substrings.
### Explanation
The core optimization is to pre-process all substrings from all words at once. We use a `HashMap<String, Set<Integer>>` where the key is a substring and the value is a `HashSet` of indices `i` corresponding to the strings `arr[i]` that contain this substring.

**Phase 1: Building the map.** We iterate through each string `arr[i]` in the input array. For each `arr[i]`, we generate all its substrings. For every substring `sub`, we add the index `i` to the set associated with `sub` in our map. If `sub` is not yet in the map, we create a new entry for it.

**Phase 2: Finding the answers.** After the map is fully populated, we iterate through each string `arr[i]` again. For each `arr[i]`, we search for its shortest uncommon substring. We generate its substrings, ordered by length from 1 to `arr[i].length()`. For each substring `sub`, we look it up in our pre-computed map. If the size of the set of indices for `sub` is 1, and that single index is `i`, it means `sub` appears only in `arr[i]` and nowhere else. This is an uncommon substring.

We collect all such uncommon substrings of the current shortest length, sort them lexicographically, and take the smallest one as the answer for `arr[i]`. Once an answer is found for a given length, we can stop searching for longer substrings for `arr[i]` and proceed to the next string.

```java
import java.util.*;

class Solution {
    public String[] shortestUncommonSubstringInArray(String[] arr) {
        int n = arr.length;
        Map<String, Set<Integer>> substringMap = new HashMap<>();

        // Phase 1: Populate the map with all substrings and their occurrences
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= arr[i].length(); len++) {
                for (int start = 0; start <= arr[i].length() - len; start++) {
                    String sub = arr[i].substring(start, start + len);
                    substringMap.computeIfAbsent(sub, k -> new HashSet<>()).add(i);
                }
            }
        }

        String[] answer = new String[n];
        // Phase 2: Find the shortest uncommon substring for each string
        for (int i = 0; i < n; i++) {
            String shortestUncommon = "";
            for (int len = 1; len <= arr[i].length(); len++) {
                List<String> candidates = new ArrayList<>();
                for (int start = 0; start <= arr[i].length() - len; start++) {
                    String sub = arr[i].substring(start, start + len);
                    if (substringMap.get(sub).size() == 1) {
                        candidates.add(sub);
                    }
                }
                if (!candidates.isEmpty()) {
                    Collections.sort(candidates);
                    shortestUncommon = candidates.get(0);
                    break;
                }
            }
            answer[i] = shortestUncommon;
        }
        return answer;
    }
}
```
### Algorithm
- 1. Create a `Map<String, Set<Integer>>` called `substringMap`.
- 2. **Populate the map:**
    - For `i` from 0 to `n-1`:
        - For `len` from 1 to `arr[i].length()`:
            - For `start` from 0 to `arr[i].length() - len`:
                - Get `sub = arr[i].substring(start, start + len)`.
                - `substringMap.computeIfAbsent(sub, k -> new HashSet<>()).add(i);`
- 3. Initialize an `answer` array of size `n`.
- 4. **Find answers:**
    - For `i` from 0 to `n-1`:
        - Initialize `foundAnswer = ""`.
        - For `len` from 1 to `arr[i].length()`:
            - Create a `List<String>` called `candidates`.
            - For `start` from 0 to `arr[i].length() - len`:
                - Get `sub = arr[i].substring(start, start + len)`.
                - If `substringMap.get(sub).size() == 1`:
                    - Add `sub` to `candidates`.
            - If `candidates` is not empty:
                - Sort `candidates` lexicographically.
                - Set `foundAnswer = candidates.get(0)`.
                - Break from the `len` loop.
        - Set `answer[i] = foundAnswer`.
- 5. Return `answer`.

## Trie-based Substring Counting
This is the most optimized approach, particularly in terms of space. It uses a Trie (prefix tree) to store all substrings from all words. Each node in the Trie stores information about which original strings contain the prefix represented by that node. By traversing the Trie, we can efficiently count the occurrences of any substring. This avoids the overhead of storing and hashing long strings as required by the HashMap approach.
**Time:** O(n * m^3). Building the Trie takes `O(n * m^2)`. Querying for all substrings for all words takes `O(n * m^3)`. The total time is dominated by the query phase. · **Space:** O(n * m^2). The number of nodes in the Trie is bounded by the total length of all unique substrings, which is `O(n * m^2)`. Each node has a constant-size pointer array and a set. The total size of all sets across all nodes is also bounded by `O(n * m^2)`.
**Pros:** Best space complexity among the presented approaches.; Potentially faster in practice than the HashMap approach due to avoiding string hashing costs for long strings.
**Cons:** More complex to implement than the HashMap approach.
### Explanation
We define a Trie data structure where each node contains an array of children (for each letter 'a' through 'z') and a `Set<Integer>` to store the indices of the strings that contain the substring represented by the path from the root to this node.

**Phase 1: Building the Trie.** We iterate through each string `arr[i]`. For each string, we generate all its suffixes (e.g., for "cab", the suffixes are "cab", "ab", "b"). We insert each of these suffixes into the Trie. During insertion, for every node we traverse (or create), we add the current string's index `i` to the node's index set. This way, after processing all strings, any path from the root to a node `p` represents a substring, and `p.indices` tells us exactly in which original strings this substring appears.

**Phase 2: Finding the answers.** After the Trie is built, we iterate through `arr[i]` one last time. For each `arr[i]`, we generate its substrings, ordered by length and then lexicographically. For each substring `sub`, we traverse the Trie to find its corresponding node. We then check the size of the `indices` set at that node. If the size is 1, it means the substring is unique to one string (which must be `arr[i]`, since `sub` is its substring). This is an uncommon substring.

As before, we find the shortest, lexicographically smallest such substring for each `arr[i]`.

```java
import java.util.*;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        Set<Integer> indices = new HashSet<>();
    }

    public String[] shortestUncommonSubstringInArray(String[] arr) {
        int n = arr.length;
        TrieNode root = new TrieNode();

        // Phase 1: Build the Trie with all substrings
        for (int i = 0; i < n; i++) {
            String s = arr[i];
            for (int j = 0; j < s.length(); j++) {
                TrieNode curr = root;
                for (int k = j; k < s.length(); k++) {
                    int charIndex = s.charAt(k) - 'a';
                    if (curr.children[charIndex] == null) {
                        curr.children[charIndex] = new TrieNode();
                    }
                    curr = curr.children[charIndex];
                    curr.indices.add(i);
                }
            }
        }

        String[] answer = new String[n];
        // Phase 2: Find the shortest uncommon substring for each string
        for (int i = 0; i < n; i++) {
            String s = arr[i];
            String shortestUncommon = "";
            for (int len = 1; len <= s.length(); len++) {
                List<String> candidates = new ArrayList<>();
                for (int j = 0; j <= s.length() - len; j++) {
                    String sub = s.substring(j, j + len);
                    TrieNode curr = root;
                    for (char ch : sub.toCharArray()) {
                        int charIndex = ch - 'a';
                        curr = curr.children[charIndex];
                    }
                    if (curr.indices.size() == 1) {
                        candidates.add(sub);
                    }
                }
                if (!candidates.isEmpty()) {
                    Collections.sort(candidates);
                    shortestUncommon = candidates.get(0);
                    break;
                }
            }
            answer[i] = shortestUncommon;
        }
        return answer;
    }
}
```
### Algorithm
- 1. Define a `TrieNode` class with `TrieNode[] children` and `Set<Integer> indices`.
- 2. Create a root `TrieNode`.
- 3. **Populate the Trie:**
    - For `i` from 0 to `n-1`:
        - For `start` from 0 to `arr[i].length() - 1`:
            - Insert the suffix `arr[i].substring(start)` into the Trie.
            - During insertion, for each node along the path, add `i` to its `indices` set.
- 4. Initialize an `answer` array of size `n`.
- 5. **Find answers:**
    - For `i` from 0 to `n-1`:
        - Find the shortest, lexicographically smallest uncommon substring for `arr[i]` by generating its substrings and querying the Trie.
        - For `len` from 1 to `arr[i].length()`:
            - Find all uncommon substrings of length `len`.
            - If any are found, sort them, take the first, and break.
- 6. Return `answer`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```