Longest Palindromic Subsequence — Problem & Solution
Longest Palindromic Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Palindromic Subsequence is a medium coding problem on strings and dynamic programming, asked in Amazon, Adobe and Uber interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Adobe, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, return the length of its longest palindromic subsequence.
A subsequence is formed by deleting zero or more characters without reordering the rest.
Example 1
Input: s = "bbbab"
Output: 4
Explanation: One answer is "bbbb".
Example 2
Input: s = "cbbd"
Output: 2
Explanation: "bb".
Example 3
Input: s = "a"
Output: 1
Constraints
1 <= s.length <= 300s consists of lowercase English letters.
Hints for Longest Palindromic Subsequence
Hint 1
Define
dp[i][j]as the answer for the substrings[i..j].Hint 2
If the ends match, they can both join a palindrome built from the inside:
dp[i+1][j-1] + 2.Hint 3
Otherwise drop one end or the other and take the better result.
How to solve Longest Palindromic Subsequence
Interval DP over substrings. Matching endpoints extend an inner palindrome by two; mismatched endpoints force a choice of which one to discard.
Approach
- Let
dp[i][j]be the longest palindromic subsequence ofs[i..j], withdp[i][i] = 1. - Fill
ifromn-1down to 0 so thatdp[i+1][…]is already known. - When
s[i] == s[j], setdp[i][j] = dp[i+1][j-1] + 2. - Otherwise set
dp[i][j] = max(dp[i+1][j], dp[i][j-1]). - Return
dp[0][n-1].
Why it works
If the two ends match, there is always an optimal solution that uses both — swapping them in never shortens the answer. If they differ, at most one can appear in the palindrome, so the best solution omits one end.
Complexity
- Time —
O(n²) - Space —
O(n²), reducible to O(n)
Pitfalls
- Filling
iupward readsdp[i+1][j-1]before it is computed. - For a two-character match,
dp[i+1][j-1]refers to an empty range and must be 0 — the zero-initialised table handles it. - This is not the same as the longest palindromic substring, which must be contiguous.
Reference solution
Python
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1] if n else 0Java
public static int longestPalindromeSubseq(String s) {
int n = s.length();
if (n == 0) return 0;
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}C++
int longestPalindromeSubseq(string s) {
int n = (int) s.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}JavaScript
var longestPalindromeSubseq = function(s) {
const n = s.length;
if (n === 0) return 0;
const dp = [];
for (let i = 0; i < n; i++) dp.push(new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s.charAt(i) === s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming