LeetCode 0516. Longest Palindromic Subsequence Solution in Java, C++, Python & More | Explanation + Code

Description

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

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Solutions

Solution 1: Dynamic Programming

We define f[i][j] as the length of the longest palindromic subsequence from the i-th character to the j-th character in string s. Initially, f[i][i] = 1, and the values of other positions are all 0.

If s[i] = s[j], then f[i][j] = f[i + 1][j - 1] + 2; otherwise, f[i][j] = max(f[i + 1][j], f[i][j - 1]).

Since the value of f[i][j] is related to f[i + 1][j - 1], f[i + 1][j], and f[i][j - 1], we should enumerate i from large to small, and enumerate j from small to large.

The answer is f[0][n - 1].

The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the string s.

PythonJavaC++GoTypeScript

class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) f = [[0] * n for _ in range(n)] for i in range(n): f[i][i] = 1 for i in range(n - 1, -1, -1): for j in range(i + 1, n): if s[i] == s[j]: f[i][j] = f[i + 1][j - 1] + 2 else: f[i][j] = max(f[i + 1][j], f[i][j - 1]) return f[0][-1](code-box)

class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] f = new int[n][n]; for (int i = 0; i < n; ++i) { f[i][i] = 1; } for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { if (s.charAt(i) == s.charAt(j)) { f[i][j] = f[i + 1][j - 1] + 2; } else { f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]); } } } return f[0][n - 1]; } }(code-box)

class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); int f[n][n]; memset(f, 0, sizeof(f)); for (int i = 0; i < n; ++i) { f[i][i] = 1; } for (int i = n - 1; ~i; --i) { for (int j = i + 1; j < n; ++j) { if (s[i] == s[j]) { f[i][j] = f[i + 1][j - 1] + 2; } else { f[i][j] = max(f[i + 1][j], f[i][j - 1]); } } } return f[0][n - 1]; } };(code-box)

func longestPalindromeSubseq(s string) int { n := len(s) f := make([][]int, n) for i := range f { f[i] = make([]int, n) f[i][i] = 1 } for i := n - 2; i >= 0; i-- { for j := i + 1; j < n; j++ { if s[i] == s[j] { f[i][j] = f[i+1][j-1] + 2 } else { f[i][j] = max(f[i+1][j], f[i][j-1]) } } } return f[0][n-1] }(code-box)

function longestPalindromeSubseq(s: string): number { const n = s.length; const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0)); for (let i = 0; i < n; ++i) { f[i][i] = 1; } for (let i = n - 2; ~i; --i) { for (let j = i + 1; j < n; ++j) { if (s[i] === s[j]) { f[i][j] = f[i + 1][j - 1] + 2; } else { f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]); } } } return f[0][n - 1]; }(code-box)