Scale Engineer

Maximize Palindrome Length From Subsequences

Hard
#1621Time: O((n+m) * 2^(n+m))Space: O(2^n * n + 2^m * m)
Patterns
Dynamic Programming
Data structures
String

Prompt

You are given two strings, word1 and word2. You want to construct a string in the following manner:

  • Choose some non-empty subsequence subsequence1 from word1.
  • Choose some non-empty subsequence subsequence2 from word2.
  • Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

 

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

 

Constraints:

  • 1 <= word1.length, word2.length <= 1000
  • word1 and word2 consist of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward, yet highly inefficient, way to solve this problem is to generate all possible combinations of subsequences and check each one. We can generate every non-empty subsequence from word1 and every non-empty subsequence from word2. For each pair of subsequences, we concatenate them and check if the resulting string is a palindrome. We keep track of the maximum length found among all palindromic constructions.

Algorithm

string

Walkthrough

The algorithm proceeds as follows:

  1. Initialize maxLength = 0.
  2. Generate all non-empty subsequences of word1. Let's call this set S1.
  3. Generate all non-empty subsequences of word2. Let's call this set S2.
  4. Iterate through every subsequence sub1 in S1.
  5. For each sub1, iterate through every subsequence sub2 in S2.
  6. Construct the string s = sub1 + sub2.
  7. Check if s is a palindrome. A simple way to do this is to see if s is equal to its reverse.
  8. If s is a palindrome, update maxLength = max(maxLength, s.length()).
  9. After checking all pairs, return maxLength.

Generating all subsequences can be done with a recursive (backtracking) helper function.

import java.util.ArrayList;import java.util.List; class Solution {    public int longestPalindrome(String word1, String word2) {        List<String> subsequences1 = new ArrayList<>();        generateSubsequences(word1, 0, "", subsequences1);         List<String> subsequences2 = new ArrayList<>();        generateSubsequences(word2, 0, "", subsequences2);         int maxLength = 0;        for (String sub1 : subsequences1) {            for (String sub2 : subsequences2) {                String combined = sub1 + sub2;                if (isPalindrome(combined)) {                    maxLength = Math.max(maxLength, combined.length());                }            }        }        return maxLength;    }     private void generateSubsequences(String s, int index, String current, List<String> result) {        if (index == s.length()) {            if (!current.isEmpty()) {                result.add(current);            }            return;        }        // Exclude character at index        generateSubsequences(s, index + 1, current, result);        // Include character at index        generateSubsequences(s, index + 1, current + s.charAt(index), result);    }     private boolean isPalindrome(String s) {        int left = 0, right = s.length() - 1;        while (left < right) {            if (s.charAt(left) != s.charAt(right)) {                return false;            }            left++;            right--;        }        return true;    }}

Complexity

Time

O((n+m) * 2^(n+m))

Space

O(2^n * n + 2^m * m)

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Guaranteed to find the correct answer by exhaustively checking all possibilities.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Not feasible for the given constraints (lengths up to 1000). It will time out for inputs larger than about 15-20 characters in total length.

Solutions

class Solution {public  int longestPalindrome(String word1, String word2) {    String s = word1 + word2;    int n = s.length();    int[][] f = new int[n][n];    for (int i = 0; i < n; ++i) {      f[i][i] = 1;    }    int ans = 0;    for (int i = n - 2; i >= 0; --i) {      for (int j = i + 1; j < n; ++j) {        if (s.charAt(i) == s.charAt(j)) {          f[i][j] = f[i + 1][j - 1] + 2;          if (i < word1.length() && j >= word1.length()) {            ans = Math.max(ans, f[i][j]);          }        } else {          f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem