Given three strings <code>a</code>, <code>b</code>, and <code>c</code>, your task is to find a string that has the<strong> minimum</strong> length and contains all three strings as <strong>substrings</strong>.
<p>If there are multiple such strings, return the<em> </em><strong>lexicographically<em> </em>smallest </strong>one.</p>

<p>Return <em>a string denoting the answer to the problem.</em></p>

<p><strong>Notes</strong></p>

<ul>
	<li>A string <code>a</code> is <strong>lexicographically smaller</strong> than a string <code>b</code> (of the same length) if in the first position where <code>a</code> and <code>b</code> differ, string <code>a</code> has a letter that appears <strong>earlier </strong>in the alphabet than the corresponding letter in <code>b</code>.</li>
	<li>A <strong>substring</strong> is a contiguous sequence of characters within a string.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;abc&quot;, b = &quot;bca&quot;, c = &quot;aaa&quot;
<strong>Output:</strong> &quot;aaabca&quot;
<strong>Explanation:</strong>  We show that &quot;aaabca&quot; contains all the given strings: a = ans[2...4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and &quot;aaabca&quot; is the lexicographically smallest one.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> a = &quot;ab&quot;, b = &quot;ba&quot;, c = &quot;aba&quot;
<strong>Output:</strong> &quot;aba&quot;
<strong>Explanation: </strong>We show that the string &quot;aba&quot; contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that &quot;aba&quot; is the lexicographically smallest one.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= a.length, b.length, c.length &lt;= 100</code></li>
	<li><code>a</code>, <code>b</code>, <code>c</code> consist only of lowercase English letters.</li>
</ul>

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        strings = set([a, b, c])
        min_string = (a + b + c)
        pair_to_intersect = dict()
        to_remove = set()
        for s1 in strings:
            for s2 in strings:
                if (s1 == s2):
                    continue
                if (s1 in s2):
                    to_remove.add(s1)
                elif (s2 in s1):
                    to_remove.add(s2)
                n1_p = 0
                while (not s2.startswith(s1[n1_p:])):
                    n1_p += 1
                pair_to_intersect[(s1, s2)] = n1_p
        strings = list(strings.difference(to_remove))
        if (len(strings) == 1):
            return strings.pop()
        elif (len(strings) == 2):
            for (i, j) in permutations(range(0, 2)):
                i = strings[i]
                j = strings[j]
                i_p = pair_to_intersect[(i, j)]
                cur_string = (i[:i_p] + j)
                if (len(cur_string) < len(min_string)):
                    min_string = cur_string
                elif (len(cur_string) == len(min_string)):
                    if (cur_string < min_string):
                        min_string = cur_string
            return min_string
        elif (len(strings) == 3):
            for (i, j, k) in permutations(range(0, 3)):
                i = strings[i]
                j = strings[j]
                k = strings[k]
                i_p = pair_to_intersect[(i, j)]
                j_p = pair_to_intersect[(j, k)]
                cur_string1 = (i[:i_p] + j)
                c1_p = 0
                while (not k.startswith(cur_string1[c1_p:])):
                    c1_p += 1
                cur_string1 = (cur_string1[:c1_p] + k)
                cur_string2 = (j[:j_p] + k)
                i_p = 0
                while (not cur_string2.startswith(i[i_p:])):
                    i_p += 1
                cur_string2 = (i[:i_p] + cur_string2)
                if (len(cur_string1) < len(cur_string2)):
                    cur_string = cur_string1
                elif (len(cur_string2) < len(cur_string1)):
                    cur_string = cur_string2
                elif (cur_string1 <= cur_string2):
                        cur_string = cur_string1
                elif (cur_string2 < cur_string1):
                    cur_string = cur_string2
                if (len(cur_string) < len(min_string)):
                    min_string = cur_string
                elif (len(cur_string) == len(min_string)):
                    if (cur_string < min_string):
                        min_string = cur_string
            return min_string

245