Quick Overview

Compare both suffix-to-prefix concatenation orders, merge the longest edge overlap, and favor the original string order when overlap lengths tie.

Merge Two Strings Using the Longest Edge Overlap

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Merge two ASCII strings by combining an overlapping suffix of the first string with an equal prefix of the second. Try both possible concatenation orders and choose the order with the longer overlap. ### Function Signature `merge_edge_overlap(str1: str, str2: str) -> str` ### Rules For an order `(a, b)`, find the greatest integer `k` from zero through `min(len(a), len(b))` such that the last k characters of a equal the first k characters of b. Its merged result is a followed by b with its first k characters removed. Compare the greatest overlap for `(str1, str2)` with that for `(str2, str1)`. Use the larger overlap. If the overlap lengths are equal, use `(str1, str2)`. Only suffix-to-prefix overlap counts; a string appearing strictly inside another does not by itself permit removal. A zero-length overlap is always valid. ### Output Return the merged string for the selected order. For this exercise, empty inputs are allowed and use the same rules. ### Constraints - `0 <= len(str1), len(str2) <= 200000`. - Strings contain ASCII characters with code points 32 through 126, inclusive, including spaces and punctuation. - Comparisons are case-sensitive. - Target O(len(str1) + len(str2)) time; linear auxiliary storage is allowed. ### Examples Input: `str1 = "1234yyabc", str2 = "abcxxxx1234"` Output: `"abcxxxx1234yyabc"` The overlap in the first order is `abc`, while the reverse order overlaps on `1234`. Input: `str1 = "ab", str2 = "ba"` Output: `"aba"` Both overlap lengths are one, so the original order wins. Input: `str1 = "abc", str2 = "abc"` Output: `"abc"` Input: `str1 = "", str2 = "hi"` Output: `"hi"`

Overview: Compare both suffix-to-prefix concatenation orders, merge the longest edge overlap, and favor the original string order when overlap lengths tie.

Merge two ASCII strings into one so that an overlapping edge is written only once. For an ordered pair (a, b), define its overlap length as the greatest integer k with 0 <= k <= min(len(a), len(b)) such that the last k characters of a are exactly equal to the first k characters of b. The merged result for that order is a followed by b with its first k characters removed. A zero-length overlap is always valid, so every order has a well-defined merged result. Compute the overlap length for the order (str1, str2) and for the order (str2, str1), and return the merged result for whichever order has the larger overlap length. If the two overlap lengths are equal, use the order (str1, str2). Only a suffix-to-prefix overlap counts: a string that appears strictly inside the other string does not, by itself, permit any removal. Comparisons are case-sensitive. Empty inputs are allowed and follow exactly the same rules. ### Examples Example 1 Input: str1 = "1234yyabc", str2 = "abcxxxx1234" Output: "abcxxxx1234yyabc" Explanation: the order (str1, str2) overlaps on "abc", a length of 3, while the order (str2, str1) overlaps on "1234", a length of 4. The reverse order has the strictly larger overlap, so the answer is "abcxxxx1234" followed by "yyabc". Example 2 Input: str1 = "ab", str2 = "ba" Output: "aba" Explanation: each order overlaps on a single character, so the lengths tie and the order (str1, str2) is used: "ab" followed by "ba" with its first character removed. ### Constraints - 0 <= len(str1), len(str2) <= 200000 - Every character of str1 and str2 is an ASCII character with a code point from 32 through 126, inclusive, including spaces and punctuation. - Comparisons are case-sensitive. - Empty strings are valid inputs and follow the same rules. - Target O(len(str1) + len(str2)) time; linear auxiliary storage is allowed. - The returned string has length at most 400000, so every length and index in this problem stays well below 2^31 - 1; no 64-bit type is required.

Constraints

  • 0 <= len(str1), len(str2) <= 200000
  • Strings contain ASCII characters with code points 32 through 126, inclusive, including spaces and punctuation.
  • Comparisons are case-sensitive.
  • Empty strings are valid inputs and follow the same rules.
  • Target O(len(str1) + len(str2)) time; linear auxiliary storage is allowed.
  • The returned string has length at most 400000, so all lengths and indices fit in a 32-bit signed integer.

Examples

Input: ('', '')

Expected Output: ''

Explanation: Both strings are empty, so min(len(a), len(b)) is 0 in both orders; the overlaps tie at 0 and (str1, str2) wins, giving the empty concatenation.

Input: ('', 'hi')

Expected Output: 'hi'

Explanation: Source example. An empty first string forces overlap 0 in both orders; the tie keeps (str1, str2), so the result is '' followed by 'hi'.

Hints

  1. There are only two candidate answers: the merge for the order (str1, str2) and the merge for the order (str2, str1). Write one helper that answers 'how long is the longest suffix of a that is also a prefix of b' and call it twice.
  2. An overlap of k = 0 is always legal, so a merge always exists; the task is to find the largest legal k for an order, not the first one you happen to check.
  3. Testing every candidate k by direct character comparison degrades to quadratic time on highly repetitive inputs; joining the two strings with a delimiter that cannot appear in the input (any code point outside 32 through 126) lets a single linear scan produce the same number.

Loading coding console...

Show the approach

Approach

Both candidate answers are instances of the same subproblem, so it is solved once and called twice: given (a, b), find the greatest k <= min(len(a), len(b)) with a[len(a) - k:] == b[:k].

The helper builds s = b + SEP + a, where SEP is the character with code point 1, which cannot occur in the input because the inputs only use code points 32 through 126. It then computes the KMP prefix function pi over s, where pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i]. The answer is pi[len(s) - 1].

Correctness: pi[len(s) - 1] is the length of the longest prefix of s that also occurs as a suffix ending at the final character of a. Invariant on the separator: SEP occurs exactly once in s and never inside a or b, so a matched block of length L can neither start before the separator in the prefix nor cross it, which forces L <= len(b); and since the block is a suffix of a, L <= len(a) as well. Every such block is therefore a legal overlap length k, and the prefix function returns the maximum such length, which is exactly 'the greatest k' the statement asks for rather than merely some valid k.

Selection: with k1 = overlap(str1, str2) and k2 = overlap(str2, str1), the result is str1 + str2[k1:] when k1 >= k2 and str2 + str1[k2:] otherwise. Using >= rather than > is precisely the stated tie-break in favor of (str1, str2).

Edge cases: if either string is empty, min(len(a), len(b)) = 0, both overlaps are 0, and the answer is the plain concatenation str1 + str2 (which equals str2 when str1 is empty and str1 when str2 is empty). Identical strings overlap completely and collapse to one copy. An occurrence of one string strictly inside the other never shortens the result unless it also reaches the relevant edge. Matching is done on raw characters, so case differences and spaces or punctuation at the edges are honored. A highly repetitive pair such as 'aaaaaaaaaab' against 'aaaaaaaaaac' makes a naive comparison of every candidate k quadratic, while the prefix function keeps the whole computation linear in len(str1) + len(str2).

Time complexity:
O(len(str1) + len(str2))
Space complexity:
O(len(str1) + len(str2))