<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:
    # trie node as a dict with count and passing in a character ord start for universality
    def __init__(self, char_ord_start='a'):
        self.children = dict()
        self.count = 0
        self.ord_start = ord(char_ord_start)
        self.char_ord_start = char_ord_start

    # getter function
    def get_char_ord_index(self, char):
        return ord(char) - self.ord_start
    
    # when adding 
    def add(self, string, index):
        # get current 
        current = self
        # loop string in range 
        for s_i in range(index, len(string)):
            # get char ord index 
            char_ord_index = self.get_char_ord_index(string[s_i])
            # if not in current children 
            if char_ord_index not in current.children:
                # set into current children a new TrieNode 
                current.children[char_ord_index] = TrieNode(self.char_ord_start)
            # move to next in either case 
            current = current.children[char_ord_index]
            # update next count 
            current.count += 1 

    # removal in this case really just decrements status 
    def remove(self, string, index):
        # similar process to above except 
        current = self
        for s_i in range(index, len(string)):
            char_ord_index = self.get_char_ord_index(string[s_i])
            if char_ord_index not in current.children:
                current.children[char_ord_index] = TrieNode(self.char_ord_start)
            current = current.children[char_ord_index]
            # decrement when you reach a spot of interest 
            current.count -= 1
    
    def check(self, string, index):
        # similar again except 
        current = self 
        answer = ''
        for s_i in range(index, len(string)): 
            char_ord_index = self.get_char_ord_index(string[s_i])
            # if you hit a wall, return answer 
            if char_ord_index not in current.children:
                return answer
            else:
                # otherwise, update answer and move to next 
                answer += string[s_i]
                current = current.children[char_ord_index]
                # unless it's also a wall, in which case also return answer 
                if current.count < 1:
                    return answer
                else:
                    continue 
        # otherwise, if you made it this far and never returned anything, return string + string 
        return string + string 

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        # non-empty strings only 
        # answer is an array of strings 
        # answer[i] is the shortest substring of array[i] that does not occur 
        # as a substring in any other part of array 
        # if multiple shortest such substrings exist, answer[i] should be an empty string 
        # Trie? 
        answer = []
        root = TrieNode()
        # build a tree! 
        for string in arr:
            for index in range(len(string)):
                root.add(string, index)
        
        for string in arr:
            result = string + string 
            for index in range(len(string)):
                root.remove(string, index)
            for index in range(len(string)):
                default_answer = root.check(string, index)
                if (len(default_answer) < len(result)):
                    result = default_answer
                elif (len(default_answer) == len(result) and default_answer < result):
                    result = default_answer
                else:
                    continue
            answer.append(result if len(result) <= len(string) else '')
            for index in range(len(string)):
                root.add(string, index)
        return answer
18600