In this guide, you will get 516. Longest Palindromic Subsequence LeetCode Solution with the best time and space complexity. The solution to Longest Palindromic Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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”.
Constraints:
1 <= s.length <= 1000
s consists only of lowercase English letters.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
516. Longest Palindromic Subsequence LeetCode Solution in C++
class Solution {
public:
int longestPalindromeSubseq(string s) {
const int n = s.length();
vector<vector<int>> mem(n, vector<int>(n));
return lps(s, 0, n - 1, mem);
}
private:
// Returns the length of LPS(s[i..j]).
int lps(const string& s, int i, int j, vector<vector<int>>& mem) {
if (i > j)
return 0;
if (i == j)
return 1;
if (mem[i][j] > 0)
return mem[i][j];
if (s[i] == s[j])
return mem[i][j] = 2 + lps(s, i + 1, j - 1, mem);
return mem[i][j] = max(lps(s, i + 1, j, mem), lps(s, i, j - 1, mem));
}
}; /* code provided by PROGIEZ */
516. Longest Palindromic Subsequence LeetCode Solution in Java
class Solution {
public int longestPalindromeSubseq(String s) {
final int n = s.length();
int[][] mem = new int[n][n];
return lps(s, 0, n - 1, mem);
}
// Returns the length of LPS(s[i..j]).
private int lps(String s, int i, int j, int[][] mem) {
if (i > j)
return 0;
if (i == j)
return 1;
if (mem[i][j] > 0)
return mem[i][j];
if (s.charAt(i) == s.charAt(j))
return mem[i][j] = 2 + lps(s, i + 1, j - 1, mem);
return mem[i][j] = Math.max(lps(s, i + 1, j, mem), lps(s, i, j - 1, mem));
}
} // code provided by PROGIEZ
516. Longest Palindromic Subsequence LeetCode Solution in Python
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
"""Returns the length of LPS(s[i..j])."""
if i > j:
return 0
if i == j:
return 1
if s[i] == s[j]:
return 2 + dp(i + 1, j - 1)
return max(dp(i + 1, j), dp(i, j - 1))
return dp(0, len(s) - 1) # code by PROGIEZ
