Last updated on January 5th, 2025 at 11:59 pm
Here, we see a Longest Palindromic Subsequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming
Companies
Amazon, Uber
Level of Question
Medium
Longest Palindromic Subsequence LeetCode Solution
Table of Contents
1. Problem Statement
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”.
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Palindromic Subsequence”. This pattern is commonly used to solve problems related to finding the longest palindromic subsequence or substring in a given string. It involves dynamic programming to break the problem into smaller subproblems and solve them iteratively or recursively.
3. Code Implementation in Different Languages
3.1 Longest Palindromic Subsequence C++
class Solution {
public:
int longestPalindromeSubseqTabular(string& s) {
if(s.empty())
return 0;
const int N = s.size();
vector<vector<int> > dp(N, vector<int>(N, 0));
for(int i = 0; i < N; i++)
dp[i][i] = 1;
for(int l = 1; l < N; l++) {
for(int i = 0; i < N - l; i++) {
int j = i + l;
if((j - i + 1) == 2) {
dp[i][j] = 1 + (s[i] == s[j]);
}
else {
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 longestPalindSubseqRec(vector<vector<int> >& dp, string& s, int i, int j) {
if(i > j)
return 0;
if(i == j)
return dp[i][j] = 1;
if(dp[i][j] == -1) {
if(s[i] == s[j])
dp[i][j] = 2 + longestPalindSubseqRec(dp, s, i+1, j-1);
else
dp[i][j] = max(longestPalindSubseqRec(dp, s, i+1, j),
longestPalindSubseqRec(dp, s, i, j-1));
}
return dp[i][j];
}
int longestPalindSubseqRecDriver(string& s) {
if(s.empty())
return 0;
const int N = s.size();
vector<vector<int> > dp(N, vector<int>(N, -1));
return longestPalindSubseqRec(dp, s, 0, N-1);
}
int longestPalindromeSubseq(string s) {
return longestPalindSubseqRecDriver(s);
}
};
3.2 Longest Palindromic Subsequence Java
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] = 2 + dp[i+1][j-1];
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
3.3 Longest Palindromic Subsequence JavaScript
var longestPalindromeSubseq = function(s) {
const n = s.length;
const dp = Array(n).fill().map(() => 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] = 2 + dp[i+1][j-1];
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
};
3.4 Longest Palindromic Subsequence Python
class Solution(object):
def longestPalindromeSubseq(self, s):
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] = 2 + dp[i+1][j-1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(n²) |
| Java | O(n²) | O(n²) |
| JavaScript | O(n²) | O(n²) |
| Python | O(n²) | O(n²) |
- The code uses the Palindromic Subsequence pattern with a Dynamic Programming approach.
- The time complexity is O(n²) for all implementations due to the nested loops or recursive calls with memoization.
- The space complexity is O(n²) for all implementations due to the 2D
dptable.