leetcode 1771 - Maximize Palindrome Length From Subsequences

https://leetcode.com/problems/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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int longestPalindrome(string word1, string word2) {
string word = word1 + word2;

int size = word.size();
int dp[size][size];

int ans = 0;

for (int len = 1; len <= size; len++) {
for (int i = 0, j = i + len - 1; j < size; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else if (len == 2) {
dp[i][j] = word[i] == word[j] ? 2 : 1;
} else {
if (word[i] == word[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}

if (len > 1 && i < word1.size() && j >= word1.size() && word[i] == word[j])
ans = max(ans, dp[i][j]);
}
}

return ans;
}
};