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


        '''


        '''

        # def get_subarray(s):
        #     output = [s[i:j+1] for i in range(len(s)) for j in range(i, len(s))]
        #     return output


        # answer = [""] * len(arr)

        # for i in range(len(arr)):
        #     subarr = sorted(get_subarray(arr[i]), key=lambda x: (len(x), x))

        #     for substr in subarr:
        #         unique = True
                
        #         for j in range(len(arr)):
        #             if j != i and substr in arr[j]:
        #                 unique = False
        #                 break

        #         if unique:
        #             answer[i] = substr
        #             break

        # return answer

        # substring_count = defaultdict(int)
        # substrings_per_string = [[] for _ in arr]
        
        # # Step 1: Count all substring frequencies
        # for idx, s in enumerate(arr):
        #     seen = set()  # To avoid counting duplicate substrings within the same string multiple times
        #     for i in range(len(s)):
        #         for j in range(i + 1, len(s) + 1):
        #             substr = s[i:j]
        #             if substr not in seen:
        #                 substring_count[substr] += 1
        #                 seen.add(substr)
        #     # Optionally store all substrings per string for later use
        #     substrings_per_string[idx] = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)]
        
        # # Step 2: Find the shortest unique substring for each string
        # answer = []
        # for substrings in substrings_per_string:
        #     # Sort substrings by length to find the shortest one first
        #     substrings_sorted = sorted(substrings, key=lambda x: len(x))
        #     unique_substr = ""
        #     for substr in substrings_sorted:
        #         if substring_count[substr] == 1:
        #             unique_substr = substr
        #             break
        #     answer.append(unique_substr)
        
        # return answer

        max_len = max([len(x) for x in arr])
        sol = [""] * len(arr)
        for l in range(1, max_len + 1):
            seen = {}
            for i, x in enumerate(arr):
                for j in range(len(x) - l + 1):
                    window = x[j:j + l]
                    if seen.get(window) == None or seen.get(window) == i:
                        seen[window] = i
                    else:
                        seen[window] = -1

            # Check if we found everything
            for k in seen.keys():
                if seen[k] == -1:
                    continue
                cur_sol = sol[seen[k]]
                if len(cur_sol) == 0 or (len(k) <= len(cur_sol) and k < cur_sol):
                    sol[seen[k]] = k

            for i in range(len(arr)):
                if len(sol[i]) == 0 and len(arr[i]) > l:
                    break
                if i == len(arr) - 1:
                    return sol

        return sol

        #         # Dictionary to count the frequency of each substring across all strings
        # substring_count = defaultdict(int)
        
        # # List to store all substrings for each string in arr
        # substrings_per_string = [[] for _ in arr]
        
        # # Step 1: Count all substring frequencies
        # for idx, s in enumerate(arr):
        #     seen = set()  # To avoid counting duplicate substrings within the same string multiple times
        #     for i in range(len(s)):
        #         for j in range(i + 1, len(s) + 1):
        #             substr = s[i:j]
        #             if substr not in seen:
        #                 substring_count[substr] += 1
        #                 seen.add(substr)
        #     # Store all substrings for the current string
        #     substrings_per_string[idx] = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)]
        
        # # Step 2: Find the shortest unique substring for each string
        # answer = []
        # for substrings in substrings_per_string:
        #     # Sort substrings by length and lexicographical order
        #     substrings_sorted = sorted(substrings, key=lambda x: (len(x), x))
            
        #     unique_substr = ""
        #     for substr in substrings_sorted:
        #         if substring_count[substr] == 1:
        #             unique_substr = substr
        #             break
        #     answer.append(unique_substr)
        
        return answer

                

            

        
        
102