Longest Palindromic Subsequence
Longest Palindromic Subsequence is a medium dynamic programming problem solved with the strings pattern.
The best approach, interval dp (one row), runs in O(n²) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from lcs with the reversed string up.
Problem
Return the length of the longest subsequence of s that is a palindrome.
Examples
Example 1
- Input
s = "bbbab"- Output
4- Why
- bbbb.
Example 2
- Input
s = "cbbd"- Output
2
Constraints
1 <= s.length <= 1000; lowercase letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| LCS with the reversed string | O(n²) | O(n²) |
| Interval DP (one row) | O(n²) | O(n) |
1LCS with the reversed string
O(n²)O(n²)A palindromic subsequence reads the same backwards, so it is a common subsequence of s and its reverse.
- Return LCS(s, reverse(s)).
class Solution {
public int longestPalindromeSubseq(String s) {
String r = new StringBuilder(s).reverse().toString();
int n = s.length();
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = s.charAt(i - 1) == r.charAt(j - 1)
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][n];
}
}class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
r = s[::-1]
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i - 1][j - 1] + 1 if s[i - 1] == r[j - 1]
else max(dp[i - 1][j], dp[i][j - 1]))
return dp[n][n]class Solution {
public:
int longestPalindromeSubseq(string s) {
string r(s.rbegin(), s.rend());
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = s[i - 1] == r[j - 1]
? dp[i - 1][j - 1] + 1
: max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][n];
}
};function longestPalindromeSubseq(s) {
const r = s.split('').reverse().join('');
const n = s.length;
const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= n; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = s[i - 1] === r[j - 1]
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][n];
}2Interval DP (one row)
O(n²)O(n)dp[i][j] = LPS of s[i..j]. Equal ends: 2 + dp[i + 1][j - 1]. Otherwise max(dp[i + 1][j], dp[i][j - 1]). Go i from right to left so the needed values are ready, and keep only one row.
- For i from n - 1 down: dp[i] = 1; for j > i apply the rule.
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[] dp = new int[n];
for (int i = n - 1; i >= 0; i--) {
dp[i] = 1;
int diag = 0; // dp[i + 1][j - 1] from the previous row
for (int j = i + 1; j < n; j++) {
int old = dp[j];
dp[j] = s.charAt(i) == s.charAt(j) ? diag + 2 : Math.max(dp[j], dp[j - 1]);
diag = old;
}
}
return dp[n - 1];
}
}class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [0] * n
for i in range(n - 1, -1, -1):
dp[i] = 1
diag = 0 # dp[i + 1][j - 1] from the previous row
for j in range(i + 1, n):
old = dp[j]
dp[j] = diag + 2 if s[i] == s[j] else max(dp[j], dp[j - 1])
diag = old
return dp[n - 1]class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<int> dp(n, 0);
for (int i = n - 1; i >= 0; i--) {
dp[i] = 1;
int diag = 0; // dp[i + 1][j - 1] from the previous row
for (int j = i + 1; j < n; j++) {
int old = dp[j];
dp[j] = s[i] == s[j] ? diag + 2 : max(dp[j], dp[j - 1]);
diag = old;
}
}
return dp[n - 1];
}
};function longestPalindromeSubseq(s) {
const n = s.length;
const dp = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
dp[i] = 1;
let diag = 0; // dp[i + 1][j - 1] from the previous row
for (let j = i + 1; j < n; j++) {
const old = dp[j];
dp[j] = s[i] === s[j] ? diag + 2 : Math.max(dp[j], dp[j - 1]);
diag = old;
}
}
return dp[n - 1];
}Edge cases to test
- Single character (1)
- Already a palindrome
Hints
Hint 1
LPS(s) = LCS(s, reverse(s)). Or use interval DP on dp[i][j] for s[i..j].
FAQ
What is the best time complexity for Longest Palindromic Subsequence?
Interval DP (one row) runs in O(n²) time and O(n) extra space.
Which pattern does Longest Palindromic Subsequence use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Minimum Insertion Steps to Make a String Palindrome.
Is there a brute force solution for Longest Palindromic Subsequence?
Yes. LCS with the reversed string takes O(n²) time and O(n²) space. A palindromic subsequence reads the same backwards, so it is a common subsequence of s and its reverse.
Which edge cases should I test for Longest Palindromic Subsequence?
Single character (1); Already a palindrome.