Last updated on October 5th, 2024 at 06:05 pm
Here, We see Longest Palindromic Subsequence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Dynamic Programming
Companies
Amazon, Uber
Level of Question
Medium
Longest Palindromic Subsequence LeetCode Solution
Table of Contents
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”.
1. Longest Palindromic Subsequence LeetCode Solution 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); } };
2. Longest Palindromic Subsequence LeetCode Solution 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. Longest Palindromic Subsequence Solution 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]; };
4. Longest Palindromic Subsequence Solution 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]