<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 TrieNode: 
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.idx_of_substring = set()

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str, idx: int) -> None:
        n = len(word)
        for i in range(n):
            itr_node = self.root
            for j in range(i, n):
                itr_node = itr_node.children[word[j]]
                itr_node.idx_of_substring.add(idx)
    
    def search(self, word: str) -> List[str]:
        n = len(word)
        # res = []
        res = ""
        for i in range(n):
            node = self.root
            # cur_str = ""
            for j in range(i, n):
                cur_str = word[i:j+ 1]
                node = node.children[word[j]]
                if len(node.idx_of_substring) == 1:
                    if cur_str == "fn" and res == "g":
                        print("here")
                    if not res or len(cur_str) < len(res):
                        res = cur_str
                        break
                    elif len(cur_str) == len(res) and cur_str < res:
                        res = cur_str
                        break

                # if len(node.idx_of_substring) == 1:
                #     res.append(cur_str)
                #     # it is guaranteed that shorter with the same first letter is smaller
                #     break
        # if not res:
        #     return ""
        # res.sort(key=lambda x : (len(x), x))
        return res


class Solution:

    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        # trie
        t = Trie()
        for idx, s in enumerate(arr):
            t.insert(s, idx)
        
        return [t.search(s) for s in arr]


        # # brute forth
        # substrings = defaultdict(set)
        # for idx, s in enumerate(arr):
        #     n = len(s)
        #     for i in range(n):
        #         for j in range(i + 1, n + 1):
        #             substrings[s[i:j]].add(idx)
        
        # res = []
        # for idx, s in enumerate(arr):
        #     n = len(s)
        #     matched = []
        #     for i in range(n):
        #         for j in range(i + 1, n + 1):
        #             if len(substrings[s[i:j]]) == 1:
        #                 matched.append(s[i:j])
        #     if not matched:
        #         res.append("")
        #     else:
        #         matched.sort(key=lambda x : (len(x), x))
        #         res.append(matched[0])
        # return res
314