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:
        strs = [a, b, c]
        result = None
        min_val = len(a) + len(b) +  len(c)
        perms = self.get_perms(3)
        for p in perms:
            r1 = self.combine_strings(strs[int(p[0])], strs[int(p[1])])
            r2 = self.combine_strings(r1, strs[int(p[2])])
            if not result: 
                min_val = len(r2)
                result = [r2]
            elif len(r2) == min_val: 
                result.append(r2)
            elif len(r2) < min_val:
                min_val = len(r2)
                result = [r2]
        result.sort()
        return result[0]

    def combine_strings(self, a, b):
        for x in range(len(a)):
            if len(a) - x >= len(b):
                if a[x:x+len(b)] == b:
                    return a
            else:
                to_check = len(a) - x
                if a[x:] == b[:to_check]:
                    return a + b[to_check:]
        return a + b

    def get_perms(self, num):
        perms = []
        stack = [str(x) for x in range(num)]
        while stack:
            curr = stack.pop(0)
            if len(curr) == num:
                perms.append(curr)
                continue
            for x in range(num):
                if str(x) not in curr:
                    stack.append(str(x) + curr)
                    stack.append(curr + str(x))
        perms = list(set(perms))
        return perms

                


295