Longest Palindromic Subsequence solution and explanation
TCS
Infosys
Google
9 more videos on this problem
DP 28. Longest Palindromic Subsequencetake U forward · 9:38 · 457K views
Longest Palindromic SubsequenceTushar Roy - Coding Made Simple · 9:18 · 330K views
Longest Palindromic Subsequence - Leetcode 516 - PythonNeetCodeIO · 18:04 · 51K views
Longest Palindromic Subsequence | Recursion | Memo | Bottom Up | Leetcode 516codestorywithMIK · 16:40 · 15K views
LeetCode 516. Longest Palindromic Subsequence Explanation and Solutionhappygirlzt · 10:02 · 3K views
[Java] Leetcode 516. Longest Palindromic Subsequence [DP Subsequence #2]Eric Programming · 23:36 · 2K views
Longest Palindromic Subsequence - Leetcode 516 - PythonTechError · 15:20 · 899 views
Longest Palindromic Subsequence - LeetCode 516 - Python SolutionCode with Carter · 11:08 · 434 views
LeetCode 516. Longest Palindromic Subsequence | Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 10:16 · 420 views
Longest Palindromic Subsequence - Leetcode 516 - JavaScriptAnkit Saxena · 7:09 · 272 views
The problem
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 <= 1000sconsists only of lowercase English letters.
Approach overview
Problem Overview: Given a string s, return the length of the longest subsequence that reads the same forward and backward. Unlike substrings, subsequences do not need to be contiguous, so you can skip characters while preserving order.
This problem appears frequently in string and dynamic programming interviews. The key observation: if the first and last characters of a substring match, they can contribute to a palindrome. Otherwise, you must skip one side and try smaller subproblems.
Approach 1: Recursive Approach with Memoization (Top-Down DP) (Time: O(n2), Space: O(n2))
Define a recursive function dfs(i, j) that returns the longest palindromic subsequence within the substring s[i..j]. If s[i] == s[j], those characters form the ends of a palindrome, so the answer becomes 2 + dfs(i+1, j-1). If they differ, skip one side and compute max(dfs(i+1, j), dfs(i, j-1)). Without optimization this recursion explodes exponentially, because the same ranges repeat many times.
Memoization fixes this by caching results for each pair (i, j). Since there are only n * n possible substrings, the recursion runs in O(n²) time and stores results in an O(n²) memo table. This approach is intuitive because it mirrors the mathematical recurrence directly.
Approach 2: Dynamic Programming (Bottom-Up Table) (Time: O(n2), Space: O(n2))
The bottom-up version fills a DP table where dp[i][j] represents the length of the longest palindromic subsequence in s[i..j]. Start with base cases where every single character is a palindrome of length 1. Then expand the window size from smaller substrings to larger ones.
For each pair of indices:
If s[i] == s[j], extend the inner palindrome: dp[i][j] = 2 + dp[i+1][j-1]. If they differ, carry forward the best subsequence by skipping one side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
The table is typically filled from the bottom of the string toward the start so that subproblems like dp[i+1][j-1] are already computed. This produces the final answer at dp[0][n-1]. Because every substring pair is processed exactly once, the runtime is O(n²) and the memory cost is also O(n²).
Another useful insight: the problem is equivalent to computing the Longest Common Subsequence between the string and its reverse. That perspective often helps when connecting multiple dynamic programming patterns together.
Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. It shows you understand overlapping subproblems, table construction, and state transitions. Starting with the recursive relation demonstrates intuition, then converting it to memoization or a DP table shows strong problem‑solving discipline.
Approach 1: Dynamic Programming Approach
Use a 2D table to keep track of the longest palindromic subsequence. The idea is to fill out this table by solving smaller subproblems and using their results to build up solutions to bigger ones.
The table, dp[i][j], will store the length of the longest palindromic subsequence in s[i...j]. Start by assuming that each character is a palindrome of length 1, and fill the table based on whether the characters at the current indices are the same.
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 __name__ == "__main__":
print(longestPalindromeSubseq("bbbab"))class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
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];
}
}
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.longestPalindromeSubseq("bbbab"));
}
}#include <iostream>
#include <vector>
using namespace std;
int longestPalindromeSubseq(string s) {
int n = s.length();
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];
}
int main() {
cout << longestPalindromeSubseq("bbbab") << endl;
return 0;
}function longestPalindromeSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => 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[i] === s[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];
}
console.log(longestPalindromeSubseq("bbbab"));#include <stdio.h>
#include <string.h>
int longestPalindromeSubseq(char *s) {
int n = strlen(s);
int dp[n][n];
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] = (dp[i + 1][j] > dp[i][j - 1]) ? dp[i + 1][j] : dp[i][j - 1];
}
}
return dp[0][n - 1];
}
int main() {
char *s = "bbbab";
printf("%d\n", longestPalindromeSubseq(s));
return 0;
}using System;
public class Solution {
public int LongestPalindromeSubseq(string s) {
int n = s.Length;
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[i] == s[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];
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.LongestPalindromeSubseq("bbbab"));
}
}Python's list comprehension is used to initialize the dp table, and the algorithm fills in the table similarly to other implementations.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 2: Recursive Approach with Memoization
This approach defines a recursive function that explores all potential palindromic subsequences, using memoization to store results of overlapping subproblems, thereby avoiding redundant calculations. The function checks if the characters at current indices are equal and proceeds based on that, with memoization avoiding recalculations.
def longestPalindromeSubseq(s: str) -> int:
def helper(l, r):
if l > r:
return 0
if l == r:
return 1
if memo[l][r] is not None:
return memo[l][r]
if s[l] == s[r]:
memo[l][r] = 2 + helper(l + 1, r - 1)
else:
memo[l][r] = max(helper(l + 1, r), helper(l, r - 1))
return memo[l][r]
n = len(s)
memo = [[None] * n for _ in range(n)]
return helper(0, n - 1)
if __name__ == "__main__":
print(longestPalindromeSubseq("bbbab"))class Solution {
private Integer[][] memo;
public int longestPalindromeSubseq(String s) {
int n = s.length();
memo = new Integer[n][n];
return helper(s, 0, n - 1);
}
private int helper(String s, int l, int r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l][r] != null) return memo[l][r];
if (s.charAt(l) == s.charAt(r)) {
memo[l][r] = 2 + helper(s, l + 1, r - 1);
} else {
memo[l][r] = Math.max(helper(s, l + 1, r), helper(s, l, r - 1));
}
return memo[l][r];
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.longestPalindromeSubseq("bbbab"));
}
}#include <iostream>
#include <vector>
using namespace std;
class Solution {
vector<vector<int>> memo;
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
memo.resize(n, vector<int>(n, -1));
return helper(s, 0, n - 1);
}
int helper(string &s, int l, int r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l][r] != -1) return memo[l][r];
if (s[l] == s[r]) {
memo[l][r] = 2 + helper(s, l + 1, r - 1);
} else {
memo[l][r] = max(helper(s, l + 1, r), helper(s, l, r - 1));
}
return memo[l][r];
}
};
int main() {
Solution solution;
cout << solution.longestPalindromeSubseq("bbbab") << endl;
return 0;
}function longestPalindromeSubseq(s) {
const n = s.length;
const memo = Array.from({ length: n }, () => Array(n).fill(null));
function helper(l, r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l][r] !== null) return memo[l][r];
if (s[l] === s[r]) {
memo[l][r] = 2 + helper(l + 1, r - 1);
} else {
memo[l][r] = Math.max(helper(l + 1, r), helper(l, r - 1));
}
return memo[l][r];
}
return helper(0, n - 1);
}
console.log(longestPalindromeSubseq("bbbab"));using System;
public class Solution {
private int?[,] memo;
public int LongestPalindromeSubseq(string s) {
int n = s.Length;
memo = new int?[n, n];
return Helper(s, 0, n - 1);
}
private int Helper(string s, int l, int r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l, r] != null) return memo[l, r].Value;
if (s[l] == s[r]) {
memo[l, r] = 2 + Helper(s, l + 1, r - 1);
} else {
memo[l, r] = Math.Max(Helper(s, l + 1, r), Helper(s, l, r - 1));
}
return memo[l, r].Value;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.LongestPalindromeSubseq("bbbab"));
}
}In the recursive approach, a helper function checks the characters from both ends of the string, memoizing already computed results to reduce computational overhead. The "memo" array stores results of already solved subproblems.
Time Complexity: O(n^2), where n is the length of the string due to memoization.
Space Complexity: O(n^2) for the memoization table.
Approach 3: 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.
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];
}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]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2) |
| Recursive Approach with Memoization | Time Complexity: O(n^2), where n is the length of the string due to memoization. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization (Top-Down DP) | O(n^2) | O(n^2) | When you want a direct implementation of the recursive recurrence and easier reasoning about subproblems. |
| Dynamic Programming Table (Bottom-Up) | O(n^2) | O(n^2) | Preferred in interviews for predictable iteration order and avoiding recursion overhead. |
Frequently asked questions
Is Longest Palindromic Subsequence easy or hard?
The problem is classified as Medium because recognizing the DP state is the main challenge. Once you identify dp[i][j] for substring ranges and define the correct recurrence, the implementation becomes straightforward.
Longest Palindromic Subsequence Python/Java solution
Most implementations use a 2D DP array or memoization map. Python solutions typically use a list-of-lists DP table or functools.lru_cache for recursion, while Java solutions use a 2D int array and nested loops to fill substring ranges.
How to solve Longest Palindromic Subsequence in O(n^2)?
Use dynamic programming over substrings. Define dp[i][j] as the longest palindromic subsequence between indices i and j. If s[i] equals s[j], extend the inner result with 2 + dp[i+1][j-1]; otherwise take max(dp[i+1][j], dp[i][j-1]). Filling the table for all pairs yields an O(n^2) solution.
What is the best approach for Longest Palindromic Subsequence?
Dynamic programming is the standard approach. Build a DP table where dp[i][j] represents the longest palindromic subsequence in substring s[i..j]. By comparing characters at both ends and reusing previously computed results, the solution runs in O(n^2) time with O(n^2) space.
Is Longest Palindromic Subsequence asked at Google/Amazon/Meta?
Longest Palindromic Subsequence appears frequently in interviews at companies like Amazon, Google, and Meta because it tests dynamic programming fundamentals. Candidates must identify overlapping subproblems and design the correct DP state transition.
What data structure is used in Longest Palindromic Subsequence?
The primary data structure is a 2D dynamic programming table (matrix) that stores results for substring ranges. In top-down solutions, the same structure appears as a memoization cache keyed by index pairs.
What is the time complexity of Longest Palindromic Subsequence?
The optimal dynamic programming solution runs in O(n^2) time because every substring pair (i, j) is evaluated once. The DP table stores results for n^2 states, leading to O(n^2) space complexity as well.