How to use the Tabulation technique of Dynamic programming to find LPS In Data Structures and Algorithms
In the earlier sections, we discussed recursive and dynamic programming approaches with memoization for solving the Longest Palindromic Subsequence (LPS) problem. Now, we will shift our focus to the Bottom-up dynamic programming method.
Below is the implementation for the above approach:
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence
#include <algorithm>
#include <cstring> // for memset
#include <iostream>
#include <string>
using namespace std;
int longestPalinSubseq(string S)
{
string R = S;
reverse(R.begin(), R.end());
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int dp[S.length() + 1][R.length() + 1];
// Initialize dp array with zeros
memset(dp, 0, sizeof(dp));
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S[i - 1] == R[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.length()][R.length()];
}
// Driver code
int main()
{
string s = "w3wiki";
cout << "The length of the LPS is "
<< longestPalinSubseq(s) << endl;
return 0;
}
// This code is contributed by akshitaguprzj3
// A Dynamic Programming based Java program for LPS problem
// Returns the length of the longest palindromic subsequence
import java.io.*;
import java.util.*;
class GFG {
public static int longestPalinSubseq(String S)
{
String R
= new StringBuilder(S).reverse().toString();
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int dp[][]
= new int[S.length() + 1][R.length() + 1];
// Filling up DP table based on conditions discussed
// in above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S.charAt(i - 1) == R.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1],
dp[i - 1][j]);
}
}
// At the end DP table will contain the LPS
// So just return the length of LPS
return dp[S.length()][R.length()];
}
// Driver code
public static void main(String[] args)
{
String s = "w3wiki";
System.out.println("The length of the LPS is "
+ longestPalinSubseq(s));
}
}
def longestPalinSubseq(S):
R = S[::-1]
# dp[i][j] will store the length of the longest
# palindromic subsequence for the substring
# starting at index i and ending at index j
dp = [[0] * (len(R) + 1) for _ in range(len(S) + 1)]
# Filling up DP table based on conditions discussed
# in the above approach
for i in range(1, len(S) + 1):
for j in range(1, len(R) + 1):
if S[i - 1] == R[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
# At the end, DP table will contain the LPS
# So just return the length of LPS
return dp[len(S)][len(R)]
# Driver code
s = "w3wiki"
print("The length of the LPS is", longestPalinSubseq(s))
# This code is contributed by shivamgupta310570
using System;
public class GFG {
// Function to find the length of the longest
// palindromic subsequence
static int LongestPalinSubseq(string S)
{
char[] charArray = S.ToCharArray();
Array.Reverse(charArray);
string R = new string(charArray);
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int[, ] dp = new int[S.Length + 1, R.Length + 1];
// Initialize dp array with zeros
for (int i = 0; i <= S.Length; i++) {
for (int j = 0; j <= R.Length; j++) {
dp[i, j] = 0;
}
}
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.Length; i++) {
for (int j = 1; j <= R.Length; j++) {
if (S[i - 1] == R[j - 1])
dp[i, j] = 1 + dp[i - 1, j - 1];
else
dp[i, j] = Math.Max(dp[i, j - 1],
dp[i - 1, j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.Length, R.Length];
}
// Driver code
public static void Main(string[] args)
{
string s = "w3wiki";
Console.WriteLine("The length of the LPS is "
+ LongestPalinSubseq(s));
}
}
// This code is contributed by shivamgupta310570
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence
function longestPalinSubseq(S)
{
let R = S.split('').reverse().join('');
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
// Initialize dp array with zeros
let dp = new Array(S.length + 1).fill(0).map(() => new Array(R.length + 1).fill(0));
// Filling up DP table based on conditions discussed
// in the above approach
for (let i = 1; i <= S.length; i++) {
for (let j = 1; j <= R.length; j++) {
if (S[i - 1] == R[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.length][R.length];
}
// Driver code
let s = "w3wiki";
console.log("The length of the LPS is " + longestPalinSubseq(s));
Output
The length of the LPS is 5
Time Complexity : O(n2)
Auxiliary Space: O(n2), since we use a 2-D array.
Longest Palindromic Subsequence (LPS)
Given a string ‘S’, find the length of the Longest Palindromic Subsequence in it.
The Longest Palindromic Subsequence (LPS) is the problem of finding a maximum-length subsequence of a given string that is also a Palindrome.
Longest Palindromic Subsequence
Examples:
Input: S = “w3wiki”
Output: 5
Explanation: The longest palindromic subsequence we can get is of length 5. There are more than 1 palindromic subsequences of length 5, for example: EEKEE, EESEE, EEFEE, …etc.Input: S = “BBABCBCAB”
Output: 7
Explanation: As “BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.
Contact Us