Longest Palindromic Subsequence is the most asked dynamic programming question in a coding interview for FAANG. So, today we will be discussing the algorithm and how you can solve this question using DP in C++, JAVA, and Python.
Question: Longest Palindromic Subsequence
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".
Solution For Longest Palindromic Subsequence
To solve this problem in the most efficient way we need to use a dynamic programming algorithm. We will break the problem into the smallest problem, solve them first, and then use the bottom-up approach to solve bigger problems.
Below Code have a runtime Complexity of O(n2) and Space Complexity of O(n).
//C++ Code Example class Solution { public: int longestPalindromeSubseq(string s) { if (s.empty()) return 0; vector<vector<int>> longest(s.size(), vector<int>(s.size())); for (int len=1; len<=s.size(); len++) { for (int i=0; i+len<=s.size(); i++) { int j = i+len-1; if (i == j) { longest[i][j] = 1; } else if (i+1 == j) { longest[i][j] = (s[i] == s[j]) ? 2 : 1; } else { int add = s[i] == s[j] ? 2 : 0; longest[i][j] = max(max(longest[i][j-1], longest[i+1][j]), longest[i+1][j-1] + add); } } } return longest[0].back(); } };
Python Solution:
#Python Code Example class Solution(object): def longestPalindromeSubseq(self, s): """ :type s: str :rtype: int """ if s == s[::-1]: return len(s) n = len(s) dp = [[0 for j in xrange(n)] for i in xrange(n)] for i in xrange(n-1, -1, -1): dp[i][i] = 1 for j in xrange(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]
JAVA Solution:
//JAVA Code Example // Its a Typical DP Problem. All you need is to have a basic Dynamic Programming Knowledge. public class Solution { public int longestPalindromeSubseq(String s) { int n=s.length(); int[][] a=new int[n][n]; for(int i=0;i<n;i++) a[i][i]=1; return helper(a,0,n-1,s); } private int helper(int[][] a,int i,int j,String s){ if(i>j || a[i][j]!=0) return a[i][j]; if(s.charAt(i)==s.charAt(j)) a[i][j]=helper(a,i+1,j-1,s)+2; else a[i][j]=Math.max(helper(a,i,j-1,s),helper(a,i+1,j,s) ); return a[i][j]; } }

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Wanna read more interview-related questions? Check Top Interview Questions category.