FastPrepMerge Two Strings by Maximum Boundary Overlap
Problem · String

Merge Two Strings by Maximum Boundary Overlap

Learn this problem
● MediumApple logoAppleFULLTIMEOA

Problem statement

You are given two ASCII strings, str1 and str2. Merge them in one of the two possible orders while writing the boundary overlap only once.

For an ordered pair (first, second), its boundary overlap is the largest integer k such that:

  • 0 <= k <= min(first.length, second.length), and
  • the suffix of first with length k equals the prefix of second with length k.

The merge for that order is first + second.substring(k). Compare the overlap for str1 followed by str2 with the overlap for str2 followed by str1.

  • Return the merge with the larger boundary overlap.
  • If both overlaps have the same length, return the merge with str1 first.
  • A boundary overlap may contain the entire shorter string.

Function

factorizeExtremities(str1: String, str2: String) → String

Examples

Example 1

str1 = "1234yyabc"str2 = "abcxxxx1234"return = "abcxxxx1234yyabc"

In the order str1 then str2, the longest overlap is "abc", with length 3. In the reverse order, it is "1234", with length 4. The reverse order therefore produces "abcxxxx1234yyabc".

Example 2

str1 = "abXY"str2 = "XYab"return = "abXYab"

Both orders have an overlap of length 2: "XY" in the first order and "ab" in the reverse order. The tie rule keeps str1 first.

Example 3

str1 = "UUUUUUUUUUUUUU"str2 = "UUUUU"return = "UUUUUUUUUUUUUU"

The full five-character str2 is a boundary overlap. Both directions reach length 5, so the tie rule keeps str1 first and adds no characters.

Constraints

  • 0 <= str1.length <= 10^5.
  • 0 <= str2.length <= 10^5.
  • Every character in str1 and str2 is an ASCII character.

More Apple problems

drafts saved locally
public String factorizeExtremities(String str1, String str2) {
  // Write your code here.
}
str1"1234yyabc"
str2"abcxxxx1234"
expected"abcxxxx1234yyabc"
checking account