How to use the Memoization Technique of Dynamic Programming In Data Structures and Algorithms
The idea used here is to reverse the given input string and check the length of the longest common subsequence. That would be the answer for the longest palindromic subsequence.
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
// in seq
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
// Returns the length of the longest
// palindromic subsequence in seq
int lps(string& s1, string& s2, int n1, int n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
// Driver program to test above functions
int main()
{
string seq = "w3wiki";
int n = seq.size();
dp[n][n];
memset(dp, -1, sizeof(dp));
string s2 = seq;
reverse(s2.begin(), s2.end());
cout << "The length of the LPS is "
<< lps(s2, seq, n, n) << endl;
return 0;
}
// Java program of above approach
import java.io.*;
import java.util.*;
class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char seq[], int i, int j, int dp[][])
{
// Base Case 1: If there is only 1 character
if (i == j) {
return dp[i][j] = 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return dp[i][j] = 2;
}
// Avoid extra call for already calculated
// subproblems, Just return the saved ans from cache
if (dp[i][j] != -1) {
return dp[i][j];
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return dp[i][j]
= lps(seq, i + 1, j - 1, dp) + 2;
}
// If the first and last characters do not match
return dp[i][j] = max(lps(seq, i, j - 1, dp),
lps(seq, i + 1, j, dp));
}
/* Driver program to test above function */
public static void main(String[] args)
{
String seq = "w3wiki";
int n = seq.length();
int dp[][] = new int[n][n];
for (int[] arr : dp)
Arrays.fill(arr, -1);
System.out.printf(
"The length of the LPS is %d",
lps(seq.toCharArray(), 0, n - 1, dp));
}
}
// This code is contributed by gauravrajput1
# A Dynamic Programming based Python program for LPS problem
# Returns the length of the longest palindromic subsequence
# in seq
dp = [[-1 for i in range(1001)]for j in range(1001)]
# Returns the length of the longest palindromic subsequence
# in seq
def lps(s1, s2, n1, n2):
if (n1 == 0 or n2 == 0):
return 0
if (dp[n1][n2] != -1):
return dp[n1][n2]
if (s1[n1 - 1] == s2[n2 - 1]):
dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)
return dp[n1][n2]
else:
dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))
return dp[n1][n2]
# Driver program to test above functions
seq = "w3wiki"
n = len(seq)
s2 = seq
s2 = s2[::-1]
print(f"The length of the LPS is {lps(s2, seq, n, n)}")
# This code is contributed by shinjanpatra
// C# code to implement the approach
using System;
using System.Numerics;
using System.Collections.Generic;
public class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char[] seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
// Driver Code
public static void Main(string[] args)
{
string seq = "w3wiki";
int n = seq.Length;
Console.Write("The length of the LPS is "
+ lps(seq.ToCharArray(), 0, n - 1));
}
}
// This code is contributed by sanjoy_62.
// A Dynamic Programming based JavaScript program for LPS problem
// Returns the length of the longest palindromic subsequence
// in seq
let dp;
// Returns the length of the longest palindromic subsequence
// in seq
function lps(s1, s2, n1, n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
/* Driver program to test above functions */
let seq = "w3wiki";
let n = seq.length;
dp = new Array(1001);
for(let i=0;i<1001;i++){
dp[i] = new Array(1001).fill(-1);
}
let s2 = seq;
s2 = s2.split('').reverse().join('');
console.log("The length of the LPS is " + lps(s2, seq, n, n),"</br>");
// This code is contributed by shinjanpatra
Output
The length of the LPS is 5
Time Complexity: O(n2)
Auxiliary Space: O(n2)
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