# 516. Longest Palindromic Subsequence

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.

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

# Solution

Approach 1: DP.

# Code (Python)

Approach 1:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # table[i][j] -- longest palindrome subseqence in s[i:j+1], table is len(s) by len(s), 
        '''
        # e.g. for 'bbbab':
        # [1, 2, 3, 3, 4]
        # [0, 1, 2, 2, 3]
        # [0, 0, 1, 1, 3]
        # [0, 0, 0, 1, 1]
        # [0, 0, 0, 0, 1]
        # Fill Order 1: fill in the upper-right half of the table, diagonally
        table = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            table[i][i] = 1

        for gap in range(1, len(s)):
            for i in range(len(s)):
                j = i + gap
                if j >= len(s):
                    break
                if s[i] != s[j]:
                    table[i][j] = max(table[i][j-1], table[i+1][j])
                else:
                    if gap == 1:
                        table[i][j] = 2
                    else:
                        table[i][j] = max(table[i][j-1], table[i+1][j], table[i+1][j-1] + 2)
        '''
        '''
        # Fill Order 2: fill in the upper-right half of the table, starting from the bottom
        table = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s) - 1, -1, -1):
            for j in range(i, len(s)):
                if i == j:
                    table[i][j] = 1
                    continue
                if s[i] != s[j]:
                    table[i][j] = max(table[i][j-1], table[i+1][j])
                else:
                    if j - i == 1:
                        table[i][j] = 2
                    else:
                        table[i][j] = max(table[i][j-1], table[i+1][j], table[i+1][j-1] + 2)
        return table[0][-1]
        '''

        # Space optimization O(N) for Fill Order 2: keep only two rows -- the current row i, and row i-1
        row = [0 for _ in range(len(s) - 1)] + [1]
        for i in range(len(s) - 2, -1, -1):
            new_row = [_ for _ in row]
            for j in range(i, len(s)):
                if i == j:
                    new_row[j] = 1
                    continue
                if s[i] != s[j]:
                    new_row[j] = max(row[j], new_row[j-1])
                else:
                    if j - i == 1:
                        new_row[j] = 2
                    else:
                        new_row[j] = max(row[j], new_row[j-1], row[j-1] + 2)
            row = new_row
        return row[-1]

# Code (C++)

Approach 1:

Approach 2: