4.Longest Palindromic Subsequence

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

Solution: (DP)

class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {

        int n = s.length();
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }
        int arr[n][n];

        for (int i = 0; i < s.length(); i++)
        {
            arr[i][i] = 1;
        }

        for (int i = 0; i <= s.length() - 2; i++)
        {
            if (s[i] != s[i + 1])
            {
                arr[i][i + 1] = 1;
            }
            else
            {
                arr[i][i + 1] = 2;
            }
        }

        for (int k = 3; k <= n; k++)
        {

            for (int i = 0; i < n - k + 1; i++)
            {
                if (s[i] == s[i + k - 1])
                {
                    arr[i][i + k - 1] = 2 + arr[i + 1][i + k - 2];
                }
                else
                {
                    arr[i][i + k - 1] = max(arr[i][i + k - 2], arr[i + 1][i + k - 1]);
                }
            }
        }

        return arr[0][n - 1];
    }
};

• Time complexity: O(n^2). Two nested traversals are needed.

• Auxiliary Space: O(n^2). Matrix of size n*n is needed to store the dp array.