1897. Maximize Palindrome Length From Subsequences¶

Difficulty: Hard

1897. Maximize Palindrome Length From Subsequences

Hard

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¶

import java.util.Arrays;

class Solution {
    private int[][] dp;

    public int longestPalindrome(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        String s = word1 + word2;
        dp = new int[n + m][n + m];
        for (int[] row : dp)
            Arrays.fill(row, -1);

        fillDp(0, n + m - 1, s);

        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (word1.charAt(i) == word2.charAt(j))
                    res = Math.max(res, dp[i][n + j]);
            }
        }
        return res;
    }

    private int fillDp(int i, int j, String s) {
        if (i > j)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];

        if (s.charAt(i) == s.charAt(j))
            return dp[i][j] = (i == j ? 1 : 2) + fillDp(i + 1, j - 1, s);
        return dp[i][j] = Math.max(fillDp(i + 1, j, s), fillDp(i, j - 1, s));
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here