Shortest superstring

Write codeHard30 min

Your task

Given exactly two lowercase strings a and b, return the shortest string that contains both a and b as substrings, maximizing their overlap. If neither is a substring of the other, merge them on their largest overlap (a's suffix with b's prefix, or b's suffix with a's prefix), choosing whichever yields the shorter result; ties may return either valid superstring. Lengths up to a few hundred.

Examples

shortest_superstring_two(a: str, b: str) -> str

Example 1

Inputshortest_superstring_two("abc", "cde")

Output"abcde"