Maximize Palindrome Length From Subsequences

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.

Solution:


We could use dp to find the longest palindrome subsequence.
The hardest part is to make sure word1 and word2 are both non-empty.
The length of word is at most 1000, that gives us a hint:To make sure they are both non-empty, we could enumeratively pick one char from word1 and one char from word2 (which takes O(M * N)).
And calculate the longest palindrom between those 2 positions.
To save some time, we can pre-compute the longest palindrome dp quick look-up table from string(word1 + word2), dp[i][j] means: the longest palindrom from i to j (subsequence).


public int longestPalindrome(String word1, String word2) {
        
	int M = word1.length(), N = word2.length();
	int res = 0;

	int[][] dp = helper(word1 + word2);

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			if (word1.charAt(i) != word2.charAt(j)) continue;  // skip non-equal pair
			res = Math.max(res, 2 + dp[i + 1][M + j - 1]);
		}
	}

	return res;
}

private int[][] helper(String s) {

	int N = s.length();
	int[][] dp = new int[N][N];
	for (int i = N - 1; i >= 0; --i) {
		dp[i][i] = 1;
		for (int j = i + 1; j < N; ++j) {
			if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
			else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
		}
	}

	return dp;
}