<p>You are given an array <code>arr</code> of size <code>n</code> consisting of <strong>non-empty</strong> strings.</p>

<p>Find a string array <code>answer</code> of size <code>n</code> such that:</p>

<ul>
	<li><code>answer[i]</code> is the <strong>shortest</strong> <span data-keyword="substring">substring</span> of <code>arr[i]</code> that does <strong>not</strong> occur as a substring in any other string in <code>arr</code>. If multiple such substrings exist, <code>answer[i]</code> should be the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span>. And if no such substring exists, <code>answer[i]</code> should be an empty string.</li>
</ul>

<p>Return <em>the array </em><code>answer</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;cab&quot;,&quot;ad&quot;,&quot;bad&quot;,&quot;c&quot;]
<strong>Output:</strong> [&quot;ab&quot;,&quot;&quot;,&quot;ba&quot;,&quot;&quot;]
<strong>Explanation:</strong> We have the following:
- For the string &quot;cab&quot;, the shortest substring that does not occur in any other string is either &quot;ca&quot; or &quot;ab&quot;, we choose the lexicographically smaller substring, which is &quot;ab&quot;.
- For the string &quot;ad&quot;, there is no substring that does not occur in any other string.
- For the string &quot;bad&quot;, the shortest substring that does not occur in any other string is &quot;ba&quot;.
- For the string &quot;c&quot;, there is no substring that does not occur in any other string.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;abc&quot;,&quot;bcd&quot;,&quot;abcd&quot;]
<strong>Output:</strong> [&quot;&quot;,&quot;&quot;,&quot;abcd&quot;]
<strong>Explanation:</strong> We have the following:
- For the string &quot;abc&quot;, there is no substring that does not occur in any other string.
- For the string &quot;bcd&quot;, there is no substring that does not occur in any other string.
- For the string &quot;abcd&quot;, the shortest substring that does not occur in any other string is &quot;abcd&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == arr.length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= arr[i].length &lt;= 20</code></li>
	<li><code>arr[i]</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        # Brute-force search; Space O(n); Time O(n * m^2 * k)
        # n = number of strings, m = length of the longest string, and k is the number of substrings.
        # Brute-force search for substrings: Generate all possible substrings for each string in increasing order of length.
        # Substring uniqueness check: For each substring of a given string, check if it appears in any other string. 
        # If it's unique, we store it as the result for that string.
        # Efficient search: Use a set or other efficient data structure to store substrings of other strings 
        # to quickly check for common substrings.
        
        # # Helper function to generate all substrings of a string
        # def gen_substring(s):
        #     sub = []
        #     n = len(s) 
        #     for length in range(1, n+1): # length of substring
        #         for start in range(n - length + 1): # start index of substring
        #             sub.append(s[start:start+length])
        #     return sub
        
        # n = len(arr)
        # res = [''] * n
        # for i in range(n):
        #     # Get all substrings of arr[i]
        #     all_subs = gen_substring(arr[i])
        #     all_subs = sorted(all_subs) # Ensure lexicographically smallest order
        #     # Check each substring for uniqueness
        #     for sub in all_subs:
        #         is_unique = True
        #         for j in range(n):
        #             if i != j and sub in arr[j]:
        #                 is_unique = False
        #                 break
        #         if is_unique:
        #             res[i] += sub
        #             break
        # return res

        def generate_substrings(s):
            substrings = []
            n = len(s)
            for length in range(1, n + 1):  # Length of substrings
                for start in range(n - length + 1):  # Starting index of substring
                    substrings.append(s[start:start + length])
            return substrings
        
        n = len(arr)
        result = [''] * n
        
        for i, s in enumerate(arr):
            # Get all substrings of arr[i]
            substrings = generate_substrings(arr[i])
            substrings = sorted(substrings, key = lambda x: (len(x), x))  # Ensure lexicographically smallest order
            
            # Check each substring for uniqueness
            for substring in substrings:
                if all(i == j or substring not in ss for j, ss in enumerate(arr)):
                    result[i] = substring
                    break
        
        return result

16300