Factorize String Extremities

Problem

Write a program to "factorize" the extremities of two ASCII strings str1 and str2.

Your must return a single string, initially made from the concatenation of two given strings. The longest substring that is common between the end of the first string and the beginning of the second one must be factorized (written only once).

You must decide the concatenation order (str1 + str2 or str2 + str1) so that you get the best factorization (longest overlap).

When the same number of characters can be factorized by the two concatenation orders, prioritize str1 + str2.

Detailed Example:

With these parameters:

• str1 = "1234yyabc"
• str2 = "abcxxxx1234"

If you choose the order str1 + str2, you could factorize the substring "abc". Then, you would return "1234yyabcxxxx1234".

1234yyabc
      |||
      abcxxxx1234

But if you choose the order str2 + str1, you could factorize "1234", which is a longer substring.

      1234yyabc
      ||||
abcxxxx1234

So, the correct string to return is "abcxxxx1234yyabc".

Constraints

• 1 ≤ len(str1) ≤ 10^4
• 1 ≤ len(str2) ≤ 10^4
• Strings contain only ASCII characters
• The strings are non-empty

Examples

Example 1

Input:

str1 = "1234yyabc"
str2 = "abcxxxx1234"

Output:

"abcxxxx1234yyabc"

Explanation: str2 + str1 order gives overlap of 4 ('1234'), str1 + str2 gives overlap of 3 ('abc'). Choose str2 + str1.

Example 2

Input:

str1 = "hello"
str2 = "loworld"

Output:

"helloworld"

Explanation: str1 + str2: 'lo' overlap (2 chars). str2 + str1: no overlap. Choose str1 + str2.

Example 3

Input:

str1 = "abc"
str2 = "def"

Output:

"abcdef"

Explanation: No overlap in either direction. Default to str1 + str2.

Example 4

Input:

str1 = "aaa"
str2 = "aaa"

Output:

"aaa"

Explanation: Complete overlap in both directions (3 chars). Since equal, use str1 + str2 = 'aaa'.

Function Signature

def factorize_extremities(str1: str, str2: str) -> str:
    """
    Factorize the extremities of two strings by finding the longest
    overlap between the end of one string and the beginning of another.

    Args:
        str1: The first ASCII string
        str2: The second ASCII string

    Returns:
        The concatenated string with the longest overlap factorized
    """
    pass

Estimated Time

15-20 minutes

Tags

strings greedy string-matching medium real-interview