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 I

Number: 3793

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two strings s and t, you can form a new string by selecting any substring from s (possibly empty) and any substring from t (possibly empty) and concatenating them in order. The goal is to determine the length of the longest palindrome that can be created from such a concatenation.

Key Insights

  • Substrings from s and t, including the empty substring, can be chosen.
  • The problem lends itself to brute-force enumeration since the maximum string length is small (up to 30).
  • For every pair of substrings (one from s and one from t), concatenate and check if the resulting string is a palindrome.
  • Use a two-pointer approach to verify a candidate palindrome.
  • Keep track of the maximum palindrome length found.

Space and Time Complexity

Time Complexity: O(n² * m² * L) where n = length of s, m = length of t, and L = length of the candidate string (maximum n+m). Space Complexity: O(1) extra space.

Solution

We solve the problem using a brute-force approach:

  1. Enumerate all possible substrings of s, and for each, enumerate all possible substrings of t.
  2. Concatenate the two substrings.
  3. Check if the concatenated string is a palindrome using the two-pointer approach.
  4. Update the maximum length found if the candidate is a palindrome. This solution works efficiently given the small input size limits.

Code Solutions

def is_palindrome(candidate):
    # Use two pointers to check for palindrome.
    left, right = 0, len(candidate) - 1
    while left < right:
        if candidate[left] != candidate[right]:
            return False
        left += 1
        right -= 1
    return True

def longest_palindrome_after_substring_concatenation(s, t):
    max_length = 0
    n, m = len(s), len(t)
    # Enumerate all substrings of s (including empty ones by including i==j).
    for i in range(n + 1):
        for j in range(i, n + 1):
            substring_s = s[i:j]
            # Enumerate all substrings of t.
            for k in range(m + 1):
                for l in range(k, m + 1):
                    substring_t = t[k:l]
                    candidate = substring_s + substring_t
                    # Check if candidate is non-empty and is a palindrome.
                    if candidate and is_palindrome(candidate):
                        max_length = max(max_length, len(candidate))
    return max_length

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