We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Palindrome After Substring Concatenation II

Number: 3808

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two strings s and t, you may pick any contiguous substring from s and any contiguous substring from t and concatenate them (s‐substring comes first, then t‐substring) to form a new string. Return the length of the longest palindrome that can be formed this way.

Key Insights

  • The answer may come from a substring chosen solely from s or solely from t (since one of the substrings may be empty).
  • When using both strings, the final palindrome must have a “mirrored” structure. In particular, if you let a be the substring chosen from s and b be the substring chosen from t such that a+b is a palindrome, then there exists some length L ≥ 0 with: • The first L characters of a equal the reverse of the last L characters of b. • The “middle” remainder (the part of a after the first L characters or the part of b before those L characters) must itself be a palindrome.
  • One can “decompose” any cross-string palindrome into the form X + Y + reverse(X), where X is a contiguous string (the common “bridge”) and Y is a palindromic substring.
  • Precomputing, for each index, the longest contiguous palindrome that starts at that index (for s) or ends at that index (for t) helps “glue” the two pieces together.
  • Iterating over possible “mirrored” segments between s and t (using two pointers to expand matching portions between s and t in reverse order) leads to candidate palindromes of length 2*|X| plus an extra palindromic extension from one side.

Space and Time Complexity

Time Complexity: O(nmmin(n,m)) in the worst case – iterating over every pair (i in s, j in t) then expanding for the mirror portion. Space Complexity: O(n + m) for storing precomputed palindrome lengths for s and t.

Solution

We can break the problem into two parts. First, note that one may simply take a single substring from s or from t if it is a palindrome; so we precompute the longest palindrome (as a contiguous substring) that starts at each index in s and the longest that ends at each index in t. These precomputed arrays (lpS and lpT_end) allow us to “extend” a palindrome after a common prefix/suffix has been matched.

For the cross-string case, observe that if we choose a substring a from s and b from t such that a+b is a palindrome, then there exists an integer l ≥ 0 so that:

  • The first l characters of a equal the reverse of the last l characters of b.
  • Depending on which part is longer, the remaining part (either the suffix of a or the prefix of b) must be a palindrome. For every pair of indices i in s and j in t satisfying s[i] == t[j], we “try” to use the characters starting at s[i] and going forward and the characters in t ending at j going backwards as the matching (mirrored) portions. Using two pointers we expand from these positions (while staying in bounds and while the characters match in the “reverse” order). Let l be the maximal matching length. Then there are two ways to add an extra palindromic block:
  1. Extend the s‐side: if s has extra characters right after the matched portion, then the longest palindrome starting at index i+l (found in lpS) can be appended.
  2. Extend the t‐side: if t has extra characters before the matched portion (since we are matching from the right), then the longest palindrome ending at index j−l (found in lpT_end) can be used. The candidate answer in these cases is 2*l plus the extra palindrome length. We also keep track of the best pure substring palindrome from either s or t. The maximum over all these cases is our answer.

Code Solutions

# Python solution with detailed comments.
def longestPalindromeAfterConcat(s, t):
    n, m = len(s), len(t)
    
    # Precompute for s: lpS[i] = length of longest palindrome starting at index i in s.
    lpS = [0] * (n+1)
    for i in range(n-1, -1, -1):
        # Every single character is a palindrome.
        max_len = 1  
        # Expand from i to the right while the substring s[i:i+len] is palindrome.
        # We do a simple check expanding one by one.
        for length in range(1, n - i + 1):
            # Check if s[i:i+length] is a palindrome using two pointers.
            left, right = i, i + length - 1
            is_pal = True
            while left < right:
                if s[left] != s[right]:
                    is_pal = False
                    break
                left += 1
                right -= 1
            if is_pal:
                max_len = length
        lpS[i] = max_len

    # Precompute for t: lpT_end[j] = length of longest palindrome ending at index j in t.
    lpT_end = [0] * (m+1)
    for j in range(m):
        max_len = 1
        for length in range(1, j+2):  # length can be at most j+1 from index 0 to j
            left, right = j - length + 1, j
            is_pal = True
            while left < right:
                if t[left] != t[right]:
                    is_pal = False
                    break
                left += 1
                right -= 1
            if is_pal:
                max_len = length
        lpT_end[j] = max_len
    
    # Track the best answer.
    best = 0
    # Pure palindromic substring from s (any contiguous substring). We can use lpS.
    for i in range(n):
        best = max(best, lpS[i])
    # Pure palindromic substring from t.
    for j in range(m):
        best = max(best, lpT_end[j])
    
    # Now consider the cross-string palindrome: a from s and b from t.
    # We try every possible pair: choose starting index i in s and ending index j in t,
    # then expand for matching characters where s[i+l] == t[j-l].
    for i in range(n):
        for j in range(m):
            if s[i] != t[j]:
                continue
            l = 0
            # Expand while in bounds and while characters match in reverse order.
            while i + l < n and j - l >= 0 and s[i + l] == t[j - l]:
                l += 1
            # l has been increased one step after failure, so the maximum matching length is l.
            # Option 1: extend on the s-side.
            extra_s = 0
            if i + l < n:
                extra_s = lpS[i + l]
            candidate1 = 2 * l + extra_s
            best = max(best, candidate1)
            
            # Option 2: extend on the t-side.
            extra_t = 0
            if j - l >= 0:
                extra_t = lpT_end[j - l]
            candidate2 = 2 * l + extra_t
            best = max(best, candidate2)
            # Also, the combination with exactly the matched parts is 2*l.
            best = max(best, 2 * l)
    
    return best

# Example usage:
print(longestPalindromeAfterConcat("abcde", "ecdba"))  # Expected output: 5
← Back to All Questions