Longest Palindromic Subsequence

The longest palindromic subsequence is pretty similar to LCS problem and even the code is kind of similar. The critical part is

if (s[i] == s[j]) dp[i][j] = 2 + f(s, i+1, j-1);
else dp[i][j] = max(f(s, i+1, j), f(s, i, j-1));

Leetcode 516. Longest Palindromic Subsequence

int dp[1001][1001];
class Solution {
public:
    int f(string& s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (dp[i][j]!= -1) return dp[i][j];
        if (s[i] == s[j]) return dp[i][j] = 2 + f(s, i+1, j-1);
        return dp[i][j] = max(f(s, i+1, j), f(s, i, j-1));
    }
    int longestPalindromeSubseq(string s) {
        memset(dp, -1, sizeof dp);
        return f(s, 0, s.size()-1);
    }
};

A slightly changed problem

This is the fourth problem of the weekly Leetcode contest of Feb 20, 2021.

1771. Maximize Palindrome Length From Subsequences

A super nice explanation from [1].

“Key Notes:

• 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)”

Image source [1]

int dp[2001][2001];
class Solution {
public:
    int f(string& s, int i, int j){
        if (i > j) return 0;
        if (i == j) return 1;
        if (dp[i][j] != -1) return dp[i][j];
        if (s[i] == s[j]) return dp[i][j] = 2 + f(s, i+1, j-1);
        return dp[i][j] = max(f(s, i+1, j), f(s, i, j-1));
    }
    int longestPalindrome(string a, string b) {
        string s = a + b;
        memset(dp, -1, sizeof dp);
        int n = a.size(), m = b.size();
        int ret = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < m; ++k) {
                if (a[i] == b[k]){
                    ret = max(ret, f(s, i, n + k));
                }
            }
        }
        return ret;
    }
};

Thanks for reading.

[1]https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/discuss/1075504/Java-Detailed-Explanation-DP-Enumerate-Every-Char-Pair