Merge Strings on Edge Overlap

AppleMedium

You are given a function that joins two strings, dropping the part where the end of one matches the start of the other.

Part 1: Merge on the longest edge overlap

Given two strings str1 and str2, return the merged string formed by joining them and dropping the repeated edge.

For an ordered pair (a, b), the overlap is the greatest k with 0 <= k <= min(len(a), len(b)) such that the last k characters of a equal the first k characters of b. k = 0 always works. A copy of b sitting elsewhere inside a does not count: only the end of a against the start of b.

Compute the overlap for (str1, str2) and for (str2, str1). Merge in the order whose overlap is larger: a followed by b without its first k characters. If the two overlaps are equal, use the order (str1, str2). Empty strings overlap with k = 0, so the result is just the concatenation.

Aim for a running time linear in the total length of the two strings.

Example 1
str1
"hello wor"
str2
"world peace"
Output
"hello world peace"
Why: The last 3 characters of hello wor are wor, which are also the first 3 of world peace, so the overlap for (str1, str2) is 3. The overlap for (str2, str1) is 0, so the first order wins and world peace is added without its first 3 characters.
Example 2
str1
"ca"
str2
"ac"
Output
"cac"
Why: Merging (str1, str2) overlaps on a and gives cac; merging (str2, str1) overlaps on c and gives aca. Both overlaps are 1, so the tie rule keeps the first order and the result is cac.

Constraints

0 <= len(str1) <= 200000
0 <= len(str2) <= 200000
32 <= ord(str1[i]) <= 126
32 <= ord(str2[i]) <= 126
Comparisons are case-sensitive: 'A' and 'a' are different characters

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question