Shortest String That Contains Three Strings — LeetCode 2800 Python Solution

The problem

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

Example

Input

a = "abc", b = "bca", c = "aaa"

Output

"aaabca"

Explanation

We show that "aaabca" 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 "aaabca" is the lexicographically smallest one.

Python solution

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        def f(s: str, t: str) -> str:
            if s in t:
                return t
            if t in s:
                return s
            m, n = len(s), len(t)
            for i in range(min(m, n), 0, -1):
                if s[-i:] == t[:i]:
                    return s + t[i:]
            return s + t

        ans = ""
        for a, b, c in permutations((a, b, c)):
            s = f(f(a, b), c)
            if ans == "" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):
                ans = s
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2800. Shortest String That Contains Three Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems