<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]:
        # given an array [arr] of size [n] consisting of non-empty strings
        # Return string array [answer] of size [n] s.t.
        # 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 LEXICOGRAPHICALLY smallest
        # if no such string exists, answer[i] should be EMPTY_STRING

        # Example:
        # arr = ["cab", "ad", "bad", "c"]
        # answer = ["ab", "", "ba", ""]

        # Naive solution: 
        # Just compare all possible substrings of arr[i] with 
        # all indices of arr except arr[i], keep track of shortest, in case of 
        # tie pick lexicographically shortest

        # Time complexity: O(n * n * l * l) = O(n^2 * l^2) where l is the worst case string length
        # Space complexity: O(1) not allocating any additional space for solution

        # We can make comparison faster by storing substrings of each string in a set

        EMPTY_STRING = ""
        arr_len = len(arr)
        answer = [EMPTY_STRING] * arr_len
        substring_sets = [set() for i in range(arr_len)]

        def populate_substring_set(set, string):
            string_len = len(string)
            for i in range(string_len):
                for j in reversed(range(i, string_len)):
                    set.add(string[i: j + 1])

        for i in range(arr_len):
            populate_substring_set(substring_sets[i], arr[i])

        for i in range(arr_len):
            min_substring_len = float("inf")
            min_substring = None
            for substring in substring_sets[i]:
                j = 0
                occurs_as_substring_in_other_string = False
                while j < arr_len and not occurs_as_substring_in_other_string:
                    if i != j and substring in substring_sets[j]:
                        occurs_as_substring_in_other_string = True
                    j += 1
                if not occurs_as_substring_in_other_string:
                    if len(substring) < min_substring_len:
                        min_substring = substring
                        min_substring_len = len(substring)
                        answer[i] = substring
                    elif len(substring) == min_substring_len and substring < min_substring:
                        min_substring = substring
                        min_substring_len = len(substring)
                        answer[i] = substring                        


        return answer


        





920