<p>Given a string <code>s</code>, find <em>the longest palindromic <strong>subsequence</strong>&#39;s length in</em> <code>s</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbbab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> One possible longest palindromic subsequence is &quot;bbbb&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> One possible longest palindromic subsequence is &quot;bb&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        def sol():

            ans= [[0,0]]
            palindrome = [["" for i in range(len(s))] for k in range(len(s))]
            # for pos in range(len(s)):
            #     palindrome[pos][pos] = 1

            # for pos in range(len(s)-1):
            #     if s[pos] == s[pos+1]:
            #         palindrome[pos][pos+1] = 1
            #         ans[0] = [pos, pos+1]

            dp = {}
            #print(palindrome)
            def find_largest_pal(start, end):
                #print(start,end)
                if palindrome[start][end]:
                    return palindrome[start][end]

                if start>end or end<0 :
                    return False

                if start == end:
                    palindrome[start][end] = s[start]
                    #ans[0] = [start,end]
                    return palindrome[start][end]

                if  s[start] == s[end]:
                    #print("comming", start, end)
                    if end-start>1:
                        find_largest_pal(start+1,end-1)
                        
                        #print(palindrome)
                        #max_pal = max_pal+1
                
                        palindrome[start][end] = s[start]+palindrome[start+1][end-1]+s[end]

                    else:

                        palindrome[start][end] = s[start]+s[end]
                        #dp[(start, end)] = ans`
                        #return dp[(start,end)]
                    
                
                find_largest_pal(start,end-1)
                find_largest_pal(start+1,end)
                #print("pal,",start+1, end-1,palindrome[start][end])
                #print(palindrome[start+1][end-1], start, end)
                if not  palindrome[start][end]:
                    palindrome[start][end] = palindrome[start][end-1] if len(palindrome[start][end-1])>len(palindrome[start+1][end]) else palindrome[start+1][end]
                
                return  palindrome[start][end]

                
            
            str_pos = find_largest_pal(0, len(s)-1)
            print(palindrome)
            return len(str_pos)

        def sol():
            palindrome = [["" for i in range(len(s))] for k in range(len(s))]
            max_seq = ""
            for start in range( len(s)-1,-1,-1):
                for end in range(start,len(s)):
                    if start ==end:
                        palindrome[start][end] = s[start]

                    elif  s[start] == s[end]:
                        if end-start>1:
                            
                            palindrome[start][end] = s[start]+palindrome[start+1][end-1]+s[end]

                        else:
                            palindrome[start][end] = s[start]+s[end]
                    if not  palindrome[start][end]:
                        palindrome[start][end] = palindrome[start][end-1] if len(palindrome[start][end-1])>len(palindrome[start+1][end]) else palindrome[start+1][end]
                
                    if len(max_seq) <  len(palindrome[start][end]):
                        max_seq =palindrome[start][end]
            #print(palindrome)
            return len(max_seq)



        return sol()
210356