Formatted question description: https://leetcode.ca/all/1771.html

1771. Maximize Palindrome Length From Subsequences

Level

Hard

Description

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

Concatenate word1 and word2 to form concat, and use dynamic programming to find the palindrome subsequences of concat. For each palindrome, if the first character is from word1 and the last character is from word2 (use indices to check this), then it is a valid palindrome, so update the maximum length of palindrome subsequences. Finally, return the maximum length.

class Solution {
    public int longestPalindrome(String word1, String word2) {
        StringBuffer sb = new StringBuffer();
        sb.append(word1);
        sb.append(word2);
        String concat = sb.toString();
        int length1 = word1.length(), length2 = word2.length(), length3 = concat.length();
        int[][] dp = new int[length3][length3];
        boolean[][] twoParts = new boolean[length3][length3];
        for (int i = 0; i < length3; i++) {
            dp[i][i] = 1;
            twoParts[i][i] = false;
        }
        int maxLength = 0;
        for (int i = length3 - 2; i >= 0; i--) {
            for (int j = i + 1; j < length3; j++) {
                if (concat.charAt(i) == concat.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    twoParts[i][j] = twoParts[i + 1][j - 1];
                    if (!twoParts[i][j])
                        twoParts[i][j] = i < length1 && j >= length1;
                } else {
                    if (dp[i][j - 1] >= dp[i + 1][j]) {
                        dp[i][j] = dp[i][j - 1];
                        twoParts[i][j] = twoParts[i][j - 1];
                    }
                    if (dp[i][j - 1] <= dp[i + 1][j]) {
                        dp[i][j] = dp[i + 1][j];
                        twoParts[i][j] = twoParts[i][j] || twoParts[i + 1][j];
                    }
                }
                if (twoParts[i][j])
                    maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        return maxLength;
    }
}

############

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;
    }
}

// OJ: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/
// Time: O(MM + NN + MN)
// Space: O(MM + NN + MN)
class Solution {
public:
    int longestPalindrome(string A, string B) {
        reverse(begin(A), end(A));
        int M = A.size(), N = B.size();
        vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
        vector<vector<int>> X(A.size(), vector<int>(A.size(), 1)), Y(N, vector<int>(B.size(), 1));
        for (int len = 2; len <= M; ++len) {
            for (int i = 0; i <= M - len; ++i) {
                if (A[i] == A[i + len - 1]) X[i][i + len - 1] = 2 + (i + 1 <= i + len - 2 ? X[i + 1][i + len - 2] : 0);
                else X[i][i + len - 1] = max(X[i + 1][i + len - 1], X[i][i + len - 2]);
            }
        }
        for (int len = 2; len <= N; ++len) {
            for (int i = 0; i <= N - len; ++i) {
                if (B[i] == B[i + len - 1]) Y[i][i + len - 1] = 2 + (i + 1 <= i + len - 2 ? Y[i + 1][i + len - 2] : 0);
                else Y[i][i + len - 1] = max(Y[i + 1][i + len - 1], Y[i][i + len - 2]);
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i] == B[j]) {
                    dp[i + 1][j + 1] = 2 + max({dp[i][j], i > 0 ? X[0][i - 1] : 0, j > 0 ? Y[0][j - 1] : 0 });
                } else {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[M][N];
    }
};

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        ans = 0
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                    if i < len(word1) and j >= len(word1):
                        ans = max(ans, f[i][j])
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return ans

func longestPalindrome(word1 string, word2 string) (ans int) {
	s := word1 + word2
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		f[i][i] = 1
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				f[i][j] = f[i+1][j-1] + 2
				if i < len(word1) && j >= len(word1) && ans < f[i][j] {
					ans = f[i][j]
				}
			} else {
				f[i][j] = max(f[i+1][j], f[i][j-1])
			}
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function longestPalindrome(word1: string, word2: string): number {
    const s = word1 + word2;
    const n = s.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
    for (let i = 0; i < n; ++i) {
        f[i][i] = 1;
    }
    let ans = 0;
    for (let i = n - 2; ~i; --i) {
        for (let j = i + 1; j < n; ++j) {
            if (s[i] === s[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;
}

impl Solution {
    pub fn longest_palindrome(word1: String, word2: String) -> i32 {
        let s: Vec<char> = format!("{}{}", word1, word2).chars().collect();
        let n = s.len();
        let mut f = vec![vec![0; n]; n];
        for i in 0..n {
            f[i][i] = 1;
        }
        let mut ans = 0;
        for i in (0..n - 1).rev() {
            for j in i + 1..n {
                if s[i] == s[j] {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    if i < word1.len() && j >= word1.len() {
                        ans = ans.max(f[i][j]);
                    }
                } else {
                    f[i][j] = f[i + 1][j].max(f[i][j - 1]);
                }
            }
        }
        ans
    }
}

1771 - Maximize Palindrome Length From Subsequences

1771. Maximize Palindrome Length From Subsequences

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1771. Maximize Palindrome Length From Subsequences

Level

Description

Solution

All Problems

All Solutions