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

Maximize Palindrome Length From Subsequences

Number: 1897

Difficulty: Hard

Paid? No

Companies: Goldman Sachs

Problem Description

Given two strings word1 and word2, we want to choose one non‐empty subsequence from each and then concatenate them to form a string. The task is to find the length of the longest palindromic string (reads the same forwards and backwards) that can be constructed in this way. If no valid palindrome exists (i.e. one that uses at least one character from each word), return 0.

Key Insights

  • The result palindrome must have characters coming from both word1 and word2.
  • A natural idea is to compute the longest palindromic subsequence (LPS) of the combined string word1 + word2.
  • However, you must ensure that the chosen palindrome “crosses the boundary” between the two words (i.e. it has at least one index from word1 and one from word2).
  • Use dynamic programming to compute the LPS for any substring and then inspect candidates to ensure they include characters from both word1 and word2.

Space and Time Complexity

Time Complexity: O(n^2), where n is the total length of word1 and word2. Space Complexity: O(n^2) due to the 2D DP table used for computing the longest palindromic subsequence.

Solution

We first combine word1 and word2 into one string s and note the length of word1 (say n1). We build a DP table dp such that dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j]. The recurrence is: • If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2 (and if i == j, dp[i][j] = 1). • Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). After filling the table, we need to ensure that our palindrome includes at least one character from word1 (indices < n1) and one from word2 (indices >= n1). Thus, we iterate over all pairs i, j such that s[i] == s[j] with i in word1 and j in word2, and update our answer with dp[i][j]. If no candidate is found, return 0.

Key details: • Use a bottom-up tabulation to fill dp. • Carefully iterate over possible boundary-crossing pairs to satisfy the problem’s constraint.

Code Solutions

# Python solution
def longestPalindrome(word1: str, word2: str) -> int:
    s = word1 + word2
    n = len(s)
    n1 = len(word1)
    
    # Create dp table with dimensions n x n, initialized to 0
    dp = [[0] * n for _ in range(n)]
    
    # Base case: every single character is a palindrome of length 1.
    for i in range(n):
        dp[i][i] = 1
        
    # Build the DP table in bottom-up manner.
    # gap represents the length of substring - 1.
    for gap in range(1, n):
        for i in range(n - gap):
            j = i + gap
            if s[i] == s[j]:
                # if characters match, add 2 and add inner palindrome if any.
                dp[i][j] = 2 + (dp[i+1][j-1] if i+1 <= j-1 else 0)
            else:
                # otherwise choose the max unused character case.
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                
    result = 0
    # Check for palindromic subsequence that crosses the boundary:
    # i from word1 part (0 <= i < n1) and j from word2 part (n1 <= j < n)
    for i in range(n1):
        for j in range(n1, n):
            if s[i] == s[j]:
                result = max(result, dp[i][j])
                
    return result

# Example usage:
print(longestPalindrome("cacb", "cbba"))  # Output: 5
print(longestPalindrome("ab", "ab"))      # Output: 3
print(longestPalindrome("aa", "bb"))      # Output: 0
← Back to All Questions