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:

tex_42e36121aacaf3a41a609905b6a50f09 Longest Palindromic Subsequence using Dynamic Programming Algorithm algorithms c / c++ dynamic programming math python because any single character is a palindrome.
when l is larger than r, tex_c07e8a4b9f1eadb2cb411cc62aac068d Longest Palindromic Subsequence using Dynamic Programming Algorithm algorithms c / c++ dynamic programming math python .
when tex_1c5d9310de08b584ba36cd4f9d0f8dd0 Longest Palindromic Subsequence using Dynamic Programming Algorithm algorithms c / c++ dynamic programming math python , tex_8cdf1ee8abc94e6bd1920fed28ec974d Longest Palindromic Subsequence using Dynamic Programming Algorithm algorithms c / c++ dynamic programming math python
Otherwise, tex_0f227c5186cab509a12aac7c20928bd2 Longest Palindromic Subsequence using Dynamic Programming Algorithm algorithms c / c++ dynamic programming math python .

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
    }
};
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.

1
2
3
4
5
6
7
8
9
10
11
12
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)
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) —

GD Star Rating
loading...
654 words
Last Post: Teaching Kids Programming - Confusing Number Validation Algorithm
Next Post: Construct a Spiral Matrix using Simulation Algorithm

The Permanent URL is: Longest Palindromic Subsequence using Dynamic Programming Algorithm

Leave a Reply