# 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: