Merge Two Strings on Their Longest Overlap

You are given two strings first and second, each made of letters and digits.

Define the overlap of a string a onto a string b as the length of the longest suffix of a that is also a prefix of b. This length can be as large as the shorter of a and b, and it is 0 when no suffix of a matches any prefix of b.

Consider joining the two strings in the order first followed by second, and separately in the order second followed by first. When you join two strings in one of these orders, write their overlapping part only once instead of twice.

Return the joined string for whichever order produces the larger overlap. If both orders produce the same overlap length, return the result for the order first followed by second.

Examples

Example 1

Input: first = "1234yyabc", second = "abcxxxx1234"
Output: "abcxxxx1234yyabc"
Explanation: The overlap of first onto second is 3 ("abc"). The overlap of second onto first is 4 ("1234"). Since 4 is larger, join second followed by first and write "1234" only once: "abcxxxx" + "1234" + "yyabc".

Example 2

Input: first = "UUUUUUUUUUUUUU", second = "UUUUU"
Output: "UUUUUUUUUUUUUU"
Explanation: The overlap of first onto second is 5, the full length of second. The overlap of second onto first is also 5. Both orders tie, so join first followed by second: second is entirely absorbed into the shared part, leaving just first.

Example 3

Input: first = "abc", second = "def"
Output: "abcdef"
Explanation: Neither string's suffix matches the other's prefix, so both overlaps are 0. The two orders tie, so join first followed by second with nothing written twice.