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: Using array to build from bottom up

Time complexity: O ( n^2 ) Auxiliary Space: O ( n^2 )

Optimal Structure

Let s(i, j) be the input sequence, and lps(i, j) be the length of the longest palindromic subsequence s(i, j).

If last and first characters of s are the same, then lps(i, j) = lps(i+1, j-1) + 2. else lps(i, j) = max(lps(i, j-1), lps(i+i, j)).

// Every single character is a palindrome of length 1
lps(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (s[i] != s[j])  lps(i, j) =  max{lps(i + 1, j),lps(i, j - 1)} 

// If there are only 2 characters and both are same
Else if (j == i + 1) lps(i, j) = 2  

// If there are more than two characters, and first and last 
// characters are same
Else lps(i, j) =  lps(i + 1, j - 1) + 2

    int longestPalindromeSubseq(string &s) {
        // write your code here
        int arr[s.size()][s.size()];
        for (int i=0; i<s.size(); i++) {
            arr[i][i] = 1;
        }

        for (int l=2; l<=s.size(); l++) {
            for (int i=0; i<s.size()-l+1; i++) {
                int j = i+l-1;
                if (s[i] != s[j]) {
                    arr[i][j] = max(arr[i+1][j], arr[i][j-1]);
                } else {
                    arr[i][j] = l == 2 ? 2 : arr[i+1][j-1]+2; 
                }
            } 
        }
        return arr[0][s.size()-1];
    }