<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]:
        '''
        arr = ["cab","ad","bad","c"]
        len(arr) <= 100 = n
        len(arr[i]) <= 20 = m

        1. generate all substrings --> O(100*20*20) = O(n*m^2)

        arr[0] = "cab" --> {c,ca,cab,a,ab,b} --> {ca,cab,ab} --> {ab}
        arr[1] = "ad" --> {a,ad,d}
        arr[2] = "bad" --> {b,ba,bad,a,ad,d}
        arr[3] = "c" --> {c}

        -- and keep an array of sets for each set of substrings to do quick O(1) lookups

        2. for each index, go through corresponding substrings
        and check if they exist in the other substrings
        -- find all the substrings for an index that don't exist in the subsets of the others
        -- if duplicate exists break out of loop and go to next in set

        3. return the lexicographically smallest


        arr = ["abc","bcd","abcd"]

        "abc" = [a,ab,abc,b,bc,c]
        "bcd" = [b,bc,bcd,c,cd,d]
        "abcd" = [a,ab,abc,abcd,b,bc,bcd,c,cd,d]
        '''

        #generate all substrings and store them in array of sets

        substrings = [set() for _ in range(len(arr))]

        def generateSubStrings(index, string):
            for i in range(len(string)):
                for j in range(i,len(string)):
                    substrings[index].add(string[i:j+1])

        for index in range(len(arr)):
            generateSubStrings(index, arr[index])

        # go through corresponding substrings and check if they exist in the other ones
        res = ["" for _ in range(len(arr))]

        for index in range(len(arr)):
            smallest_str = ""
            #for each index, check each substring at index against all the other substrings
            for s in substrings[index]:
                foundDuplicate = False
                # go through all other sets of the other strings
                for j in range(len(arr)):
                    if j == index:
                        continue
                    elif s in substrings[j]:
                        foundDuplicate = True
                        break

                if not foundDuplicate:
                    #check if string is lexicographically smaller than curr smallest_str
                    if smallest_str == "" or len(s) < len(smallest_str):
                        smallest_str = s
                    elif len(s) == len(smallest_str):
                        a = 0
                        while a in range(len(smallest_str)) and a in range(len(s)) and smallest_str[a] == s[a]:
                            a += 1
                        smallest_str = s if ord(s[a]) < ord(smallest_str[a]) else smallest_str
            
            res[index] = smallest_str
        
        return res



            # find lexicographically smallest

769