Longest Palindromic Subsequence using Dynamic Programming Algorithm

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:
“bbbab”
Output:
4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:
“cbbd”
Output:
2
One possible longest palindromic subsequence is “bb”.

Constraints:
1 <= s.length <= 1000
s consists only of lowercase English letters.

Compute the Longest Palindromic Subsequence using Dynamic Programming Algorithm

Given a function F(l, r) to store the longest palindrome subsequence between index l and r, we then can compute the function based on the following conditions:

because any single character is a palindrome.
when l is larger than r, .
when ,
Otherwise, .

Given that we have DP (Dynamic Programming) equation, it is easy to implement it with a top-down approach i.e. Recursion with Memoization. See following C++ DP code using Two-Dimensional unordered_map (hash map).

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        unordered_map<int, unordered_map<int, int>> memo;
        function<int(int, int)> dp = [&](int left, int right) {
            if (left == right) {
                return 1;
            }
            if (left > right) {
                return 0;
            }
            if (memo.count(left) && memo[left].count(right)) {
                return memo[left][right];
            }
            if (s[left] == s[right]) {
                return memo[left][right] = 2 + dp(left + 1, right - 1);
            }
            return memo[left][right] = max(dp(left + 1, right), dp(left, right - 1));
        };
        return dp(0, static_cast<int>(s.size()) - 1);
    }
};

In Python, we can annoate the function with @lru_cache that allows to cache the intermediate values of DP automatically.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @lru_cache(None)
        def dp(l, r):
            if l > r:
                return 0
            if l == r:
                return 1 if s[l] == s[r] else 0
            if s[l] == s[r]:
                return 2 + dp(l + 1, r - 1)
            return max(dp(l + 1, r), dp(l, r - 1))
        return dp(0, len(s) - 1)

Time complexity is O(N^2) i.e. N^2 pairs of (l, r) and space complexity is also O(N^2).

See also: Teaching Kids Programming – Compute the Longest Palindromic Subsequence via Dynamic Programming Algorithm

–EOF (The Ultimate Computing & Technology Blog) —