Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

&nbsp;
Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".


Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 1000
	s consists only of lowercase English letters.


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0 for x in range(n)] for x in range(n)]
        for i in range(n): dp[i][i] = 1 # Single length strings are palindrome
        for chainLength in range(2, n+1):
            for i in range(0, n-chainLength+1): # Discarding the lower triangle
                j = i + chainLength - 1
                if s[i] == s[j]: 
                    if chainLength == 2: dp[i][j] = 2
                    else: dp[i][j] = dp[i+1][j-1] + 2
                else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]
class Solution {
    public int longestPalindromeSubseq(String s) {
        	StringBuilder sb = new StringBuilder(s);
    	    sb.reverse();
    	    String s2 = sb.toString();
        return longestCommonSubsequence(s,s2);
    }
     public int longestCommonSubsequence(String text1, String text2) {
        int [][]dp = new int[text1.length()+1][text2.length()+1]; 
        for(int i= text1.length()-1;i>=0;i--){
            for(int j = text2.length()-1;j>=0;j--){
                char ch1 = text1.charAt(i);
                char ch2 = text2.charAt(j);
                if(ch1==ch2) // diagnal
                dp[i][j]= 1+dp[i+1][j+1];
                else// right,down considering not matchning char from s1 and skipping s2 
                //considering not matchning char from s2 and skipping s1
                    dp[i][j] = Math.max(dp[i][j+1],dp[i+1][j]);
                    
            }
        }
        return dp[0][0];
    }
}
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        int dp[n][n];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){
            dp[i][i] = 1;
        }
        int res = 1;
        for(int j = 1; j < n; j++){
            for(int r = 0, c = j ; r < n && c < n; r++, c++){
                if(s[r] == s[c]){
                    dp[r][c] = 2+dp[r+1][c-1];
                }
                else{
                    dp[r][c] = max(dp[r][c-1],dp[r+1][c]);
                }
            }
        }
        return dp[0][n-1];
    }
};
var longestPalindromeSubseq = function(s) {
    const { length } = s;
    const dp = Array(length).fill('').map(() => Array(length).fill(0));

    for (let start = 0; start < length; start++) {
        const str = s[start];
        dp[start][start] = 1;

        for (let end = start - 1; end >= 0; end--) {
            dp[start][end] = str === s[end]
                ? dp[start - 1][end + 1] + 2
                : Math.max(dp[start - 1][end], dp[start][end + 1])
        }
    }
    return dp[length - 1][0];
};
Longest Palindromic Subsequence