1771. 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.

class Solution {
public:
    int longestPalindrome(string w1, string w2) {
        int separate = w1.length();
        w1 += w2;
        vector<vector<int>> dp(w1.length() + 1, vector<int>(w1.length() + 1, 0));
        int res = 0;
        for (int len = 1; len <= w1.size(); ++len)
            for (auto i = 0; i + len <= w1.size(); ++i) {
                if(w1[i] == w1[i + len - 1]) {
                    dp[i][i + len] = dp[i + 1][i + len - 1] + (len == 1 ? 1 : 2);
                    if(i + len - 1 >= separate && i < separate){
                        res = max(res, dp[i][i + len]);
                    }
                } else {
                    dp[i][i + len] = max(dp[i][i + len - 1], dp[i + 1][i + len]);
                }
            }
        return res;
    }
};