# 3076. Shortest Uncommon Substring in an Array

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:**

<pre><code><strong>Input: arr = ["cab","ad","bad","c"]
</strong><strong>Output: ["ab","","ba",""]
</strong><strong>Explanation: We have the following:
</strong>- 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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: arr = ["abc","bcd","abcd"]
</strong><strong>Output: ["","","abcd"]
</strong><strong>Explanation: We have the following:
</strong>- 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></pre>

&#x20;

**Constraints:**

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

分析

1. **Substring Generation**: We first generate all possible substrings for each string in the input array and count how many times each substring appears across all strings using a dictionary.
2. **Unique Substring Identification**: For each string, we then check all possible substrings (starting from the shortest length) to find those that appear exactly once in our count dictionary (meaning they're unique to that string).
3. **Result Selection**: For each string, we select the lexicographically smallest substring among the shortest unique substrings found. If no unique substring exists, we return an empty string for that position.

````
```python3
class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        res = []
        count = defaultdict(int)
        for s in arr:
            subs = set()
            n = len(s)
            for i in range(n):
                for j in range(i+1,n+1):
                    subs.add(s[i:j])
            for i in subs:
                count[i]+=1

        for s in arr:
            unique_subs = []
            length = len(s)
            # Generate all possible substrings for current string
            # 第二轮从长度最短的开始 这样可以满足条件
            for l in range(1, length + 1):
                current_subs = set()
                for i in range(length - l + 1):
                    sub = s[i:i+l]
                    if count[sub] == 1:
                        current_subs.add(sub)
                if current_subs:
                    unique_subs.append(min(current_subs))
                    break  # Since we're checking increasing lengths, first valid is shortest
            if unique_subs:
                res.append(unique_subs[0])
            else:
                res.append("")
            
        return res
                
                
                

        
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/airbnb2025/3076.-shortest-uncommon-substring-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.