Posted on by Kalkicode
Code Dynamic Programming

# Longest palindromic subsequence using dynamic programming

In computer science, finding the longest palindromic subsequence (LPS) is a classic problem that involves identifying the length of the longest subsequence that is also a palindrome within a given string. A palindrome is a sequence of characters that reads the same forwards and backwards. This article explores the concept of LPS and presents an efficient solution using dynamic programming.

## Understanding the Problem:

Given a string, the task is to find the length of the longest palindromic subsequence within it. Unlike substrings, a subsequence does not require consecutive elements, but the relative order of characters must be maintained. For example, in the string "pewmoozdp," the longest palindromic subsequence is "poop," which has a length of 4.

## Code Solution

``````/*
C program for
Longest palindromic subsequence using dynamic programming
*/
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findLPS(char *text)
{
int n = strlen(text);
if (n == 0)
{
return 0;
}
int dp[n][n];
// Set 1 to all diagonal elements
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = (k + i) - 1;
if (k == 2 && text[i] == text[j])
{
// First similar pair
dp[i][j] = 2;
}
else if (text[i] == text[j])
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = maxValue(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
int main(int argc, char
const *argv[])
{
char *text1 = "pewmoozdp";
char *text2 = "xbfdsafx";
char *text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
int ans = findLPS(text1);
printf("\n Given  : %s ", text1);
printf("\n Result : %d", ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = findLPS(text2);
printf("\n Given  : %s ", text2);
printf("\n Result : %d", ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
ans = findLPS(text3);
printf("\n Given  : %s ", text3);
printf("\n Result : %d", ans);
return 0;
}``````

#### Output

`````` Given  : pewmoozdp
Result : 4
Given  : xbfdsafx
Result : 5
Given  : abbisstiwebaccess
Result : 8``````
``````// Java program for
// Longest palindromic subsequence using dynamic programming
public class Subsequence
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findLPS(String text)
{
int n = text.length();
if (n == 0)
{
return 0;
}
int[][] dp = new int[n][n];
// Set 1 to all diagonal elements
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = (k + i) - 1;
if (k == 2 && text.charAt(i) == text.charAt(j))
{
// First similar pair
dp[i][j] = 2;
}
else if (text.charAt(i) == text.charAt(j))
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = maxValue(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
public static void main(String[] args)
{
String text1 = "pewmoozdp";
String text2 = "xbfdsafx";
String text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
System.out.print("\n Given : " + text1);
System.out.print("\n Result : " + ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
System.out.print("\n Given : " + text2);
System.out.print("\n Result : " + ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
System.out.print("\n Given : " + text3);
System.out.print("\n Result : " + ans);
}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
// C++ program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
public:
// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findLPS(string text)
{
int n = text.length();
if (n == 0)
{
return 0;
}
int dp[n][n];
// Set 1 to all diagonal elements
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = (k + i) - 1;
if (k == 2 && text[i] == text[j])
{
// First similar pair
dp[i][j] = 2;
}
else if (text[i] == text[j])
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = this->maxValue(dp[i][j - 1],
dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
};
int main()
{
string text1 = "pewmoozdp";
string text2 = "xbfdsafx";
string text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
cout << "\n Given : " << text1;
cout << "\n Result : " << ans;
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
cout << "\n Given : " << text2;
cout << "\n Result : " << ans;
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
cout << "\n Given : " << text3;
cout << "\n Result : " << ans;
return 0;
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````// Include namespace system
using System;
// Csharp program for
// Longest palindromic subsequence using dynamic programming
public class Subsequence
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findLPS(String text)
{
int n = text.Length;
if (n == 0)
{
return 0;
}
int[,] dp = new int[n,n];
// Set 1 to all diagonal elements
for (int i = 0; i < n; ++i)
{
dp[i,i] = 1;
}
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = (k + i) - 1;
if (k == 2 && text[i] == text[j])
{
// First similar pair
dp[i,j] = 2;
}
else if (text[i] == text[j])
{
// Calculate sum the bottom left element + 2
dp[i,j] = dp[i + 1,j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i,j] = this.maxValue(dp[i,j - 1], dp[i + 1,j]);
}
}
}
return dp[0,n - 1];
}
public static void Main(String[] args)
{
String text1 = "pewmoozdp";
String text2 = "xbfdsafx";
String text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
Console.Write("\n Given : " + text1);
Console.Write("\n Result : " + ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
Console.Write("\n Given : " + text2);
Console.Write("\n Result : " + ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
Console.Write("\n Given : " + text3);
Console.Write("\n Result : " + ans);
}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````package main
import "fmt"
// Go program for
// Longest palindromic subsequence using dynamic programming
type Subsequence struct {}
func getSubsequence() * Subsequence {
var me *Subsequence = &Subsequence {}
return me
}
// Returns the max value of given two numbers
func(this Subsequence) maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func(this Subsequence) findLPS(text string) int {
var n int = len(text)
if n == 0 {
return 0
}
var dp = make([][] int, n)
for i := 0; i < n; i++ {
dp[i] = make([] int, n)
}
// Set 1 to all diagonal elements
for i := 0 ; i < n ; i++ {
dp[i][i] = 1
}
for k := 2 ; k <= n ; k++ {
for i := 0 ; i < n - k + 1 ; i++ {
var j int = (k + i) - 1
if k == 2 && text[i] == text[j] {
// First similar pair
dp[i][j] = 2
} else if text[i] == text[j] {
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2
} else {
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = this.maxValue(dp[i][j - 1],
dp[i + 1][j])
}
}
}
return dp[0][n - 1]
}
func main() {
var task * Subsequence = getSubsequence()
var text1 string = "pewmoozdp"
var text2 string = "xbfdsafx"
var text3 string = "abbisstiwebaccess"
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
fmt.Print("\n Given : ", text1)
fmt.Print("\n Result : ", ans)
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
fmt.Print("\n Given : ", text2)
fmt.Print("\n Result : ", ans)
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
fmt.Print("\n Given : ", text3)
fmt.Print("\n Result : ", ans)
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````<?php
// Php program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
// Returns the max value of given two numbers
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function findLPS(\$text)
{
\$n = strlen(\$text);
if (\$n == 0)
{
return 0;
}
\$dp = array_fill(0, \$n, array_fill(0, \$n, 0));
// Set 1 to all diagonal elements
for (\$i = 0; \$i < \$n; ++\$i)
{
\$dp[\$i][\$i] = 1;
}
for (\$k = 2; \$k <= \$n; ++\$k)
{
for (\$i = 0; \$i < \$n - \$k + 1; ++\$i)
{
\$j = (\$k + \$i) - 1;
if (\$k == 2 && \$text[\$i] == \$text[\$j])
{
// First similar pair
\$dp[\$i][\$j] = 2;
}
else if (\$text[\$i] == \$text[\$j])
{
// Calculate sum the bottom left element + 2
\$dp[\$i][\$j] = \$dp[\$i + 1][\$j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
\$dp[\$i][\$j] = \$this->maxValue(\$dp[\$i][\$j - 1],
\$dp[\$i + 1][\$j]);
}
}
}
return \$dp[0][\$n - 1];
}
}

function main()
{
\$text1 = "pewmoozdp";
\$text2 = "xbfdsafx";
\$text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
echo("\n Given : ".\$text1);
echo("\n Result : ".\$ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
echo("\n Given : ".\$text2);
echo("\n Result : ".\$ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
echo("\n Given : ".\$text3);
echo("\n Result : ".\$ans);
}
main();``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````// Node JS program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
// Returns the max value of given two numbers
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
findLPS(text)
{
var n = text.length;
if (n == 0)
{
return 0;
}
var dp = Array(n).fill(0).map(() => new Array(n).fill(0));
// Set 1 to all diagonal elements
for (var i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (var k = 2; k <= n; ++k)
{
for (var i = 0; i < n - k + 1; ++i)
{
var j = (k + i) - 1;
if (k == 2 && text.charAt(i) == text.charAt(j))
{
// First similar pair
dp[i][j] = 2;
}
else if (text.charAt(i) == text.charAt(j))
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = this.maxValue(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
}

function main()
{
var text1 = "pewmoozdp";
var text2 = "xbfdsafx";
var text3 = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
process.stdout.write("\n Given : " + text1);
process.stdout.write("\n Result : " + ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
process.stdout.write("\n Given : " + text2);
process.stdout.write("\n Result : " + ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
process.stdout.write("\n Given : " + text3);
process.stdout.write("\n Result : " + ans);
}
main();``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````#  Python 3 program for
#  Longest palindromic subsequence using dynamic programming
class Subsequence :
#  Returns the max value of given two numbers
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def findLPS(self, text) :
n = len(text)
if (n == 0) :
return 0

dp = [[0] * (n) for _ in range(n) ]
i = 0
#  Set 1 to all diagonal elements
while (i < n) :
dp[i][i] = 1
i += 1

k = 2
while (k <= n) :
i = 0
while (i < n - k + 1) :
j = (k + i) - 1
if (k == 2 and text[i] == text[j]) :
#  First similar pair
dp[i][j] = 2
elif (text[i] == text[j]) :
#  Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2
else :
#  When element are not same (i and j location)
#  Then change current element by max of
#  left and down element
dp[i][j] = self.maxValue(dp[i][j - 1], dp[i + 1][j])

i += 1

k += 1

return dp[0][n - 1]

def main() :
text1 = "pewmoozdp"
text2 = "xbfdsafx"
text3 = "abbisstiwebaccess"
#  Test A
#  Text = pewmoozdp
#  "poop" is resultant palindrome
#  Length 4
print("\n Given : ", text1, end = "")
print("\n Result : ", ans, end = "")
#  Test B
#  Text = xbfdsafx
#  [xfsfx,xfdfx,xfafx] is resultant palindrome
#  Length 5
print("\n Given : ", text2, end = "")
print("\n Result : ", ans, end = "")
#  Test C
#  Text = "abbisstiwebaccess"
#  [abissiba] is resultant palindrome
#  Length 8
print("\n Given : ", text3, end = "")
print("\n Result : ", ans, end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Given :  pewmoozdp
Result :  4
Given :  xbfdsafx
Result :  5
Given :  abbisstiwebaccess
Result :  8``````
``````#  Ruby program for
#  Longest palindromic subsequence using dynamic programming
class Subsequence
#  Returns the max value of given two numbers
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def findLPS(text)
n = text.length
if (n == 0)
return 0
end

dp = Array.new(n) {Array.new(n) {0}}
i = 0
#  Set 1 to all diagonal elements
while (i < n)
dp[i][i] = 1
i += 1
end

k = 2
while (k <= n)
i = 0
while (i < n - k + 1)
j = (k + i) - 1
if (k == 2 && text[i] == text[j])
#  First similar pair
dp[i][j] = 2
elsif (text[i] == text[j])
#  Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2
else

#  When element are not same (i and j location)
#  Then change current element by max of
#  left and down element
dp[i][j] = self.maxValue(dp[i][j - 1], dp[i + 1][j])
end

i += 1
end

k += 1
end

return dp[0][n - 1]
end

end

def main()
text1 = "pewmoozdp"
text2 = "xbfdsafx"
text3 = "abbisstiwebaccess"
#  Test A
#  Text = pewmoozdp
#  "poop" is resultant palindrome
#  Length 4
print("\n Given : ", text1)
print("\n Result : ", ans)
#  Test B
#  Text = xbfdsafx
#  [xfsfx,xfdfx,xfafx] is resultant palindrome
#  Length 5
print("\n Given : ", text2)
print("\n Result : ", ans)
#  Test C
#  Text = "abbisstiwebaccess"
#  [abissiba] is resultant palindrome
#  Length 8
print("\n Given : ", text3)
print("\n Result : ", ans)
end

main()``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````import scala.collection.mutable._;
// Scala program for
// Longest palindromic subsequence using dynamic programming
class Subsequence()
{
// Returns the max value of given two numbers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def findLPS(text: String): Int = {
var n: Int = text.length();
if (n == 0)
{
return 0;
}
var dp: Array[Array[Int]] = Array.fill[Int](n, n)(0);
var i: Int = 0;
// Set 1 to all diagonal elements
while (i < n)
{
dp(i)(i) = 1;
i += 1;
}
var k: Int = 2;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
var j: Int = (k + i) - 1;
if (k == 2 && text.charAt(i) == text.charAt(j))
{
// First similar pair
dp(i)(j) = 2;
}
else if (text.charAt(i) == text.charAt(j))
{
// Calculate sum the bottom left element + 2
dp(i)(j) = dp(i + 1)(j - 1) + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp(i)(j) = maxValue(dp(i)(j - 1), dp(i + 1)(j));
}
i += 1;
}
k += 1;
}
return dp(0)(n - 1);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
var text1: String = "pewmoozdp";
var text2: String = "xbfdsafx";
var text3: String = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
print("\n Given : " + text1);
print("\n Result : " + ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
print("\n Given : " + text2);
print("\n Result : " + ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
print("\n Given : " + text3);
print("\n Result : " + ans);
}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````
``````import Foundation;
// Swift 4 program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
// Returns the max value of given two numbers
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func findLPS(_ data: String) -> Int
{
var text = Array(data);
let n: Int = text.count;
if (n == 0)
{
return 0;
}
var dp: [
[Int]
] = Array(repeating: Array(repeating: 0, count: n), count: n);
var i: Int = 0;
// Set 1 to all diagonal elements
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
var k: Int = 2;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
let j: Int = (k + i) - 1;
if (k == 2 && text[i] == text[j])
{
// First similar pair
dp[i][j] = 2;
}
else if (text[i] == text[j])
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = self.maxValue(dp[i][j - 1],
dp[i + 1][j]);
}
i += 1;
}
k += 1;
}
return dp[0][n - 1];
}
}
func main()
{
let text1: String = "pewmoozdp";
let text2: String = "xbfdsafx";
let text3: String = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
print("\n Given : ", text1, terminator: "");
print("\n Result : ", ans, terminator: "");
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
print("\n Given : ", text2, terminator: "");
print("\n Result : ", ans, terminator: "");
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
print("\n Given : ", text3, terminator: "");
print("\n Result : ", ans, terminator: "");
}
main();``````

#### Output

`````` Given :  pewmoozdp
Result :  4
Given :  xbfdsafx
Result :  5
Given :  abbisstiwebaccess
Result :  8``````
``````// Kotlin program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
// Returns the max value of given two numbers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun findLPS(text: String): Int
{
val n: Int = text.length;
if (n == 0)
{
return 0;
}
val dp: Array < Array < Int >> = Array(n)
{
Array(n)
{
0
}
};
var i: Int = 0;
// Set 1 to all diagonal elements
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
var k: Int = 2;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
val j: Int = (k + i) - 1;
if (k == 2 && text.get(i) == text.get(j))
{
// First similar pair
dp[i][j] = 2;
}
else if (text.get(i) == text.get(j))
{
// Calculate sum the bottom left element + 2
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
// When element are not same (i and j location)
// Then change current element by max of
// left and down element
dp[i][j] = this.maxValue(dp[i][j - 1], dp[i + 1][j]);
}
i += 1;
}
k += 1;
}
return dp[0][n - 1];
}
}
fun main(args: Array < String > ): Unit
{
val text1: String = "pewmoozdp";
val text2: String = "xbfdsafx";
val text3: String = "abbisstiwebaccess";
// Test A
// Text = pewmoozdp
// "poop" is resultant palindrome
// Length 4
print("\n Given : " + text1);
print("\n Result : " + ans);
// Test B
// Text = xbfdsafx
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
print("\n Given : " + text2);
print("\n Result : " + ans);
// Test C
// Text = "abbisstiwebaccess"
// [abissiba] is resultant palindrome
// Length 8
print("\n Given : " + text3);
print("\n Result : " + ans);
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5
Given : abbisstiwebaccess
Result : 8``````

## Dynamic Programming Approach:

To solve this problem efficiently, dynamic programming can be employed. Dynamic programming breaks down a complex problem into simpler overlapping subproblems, solving each subproblem only once and storing its result for future reference. This approach greatly reduces redundant computations.

The algorithm for finding the LPS using dynamic programming can be summarized as follows:

1. Create a 2D matrix, dp[n][n], where n is the length of the input string.
2. Initialize the diagonal elements of the matrix to 1 because every individual character is a palindrome of length 1.
3. Iterate through the string in a bottom-up manner, considering all possible subproblems.
4. For each substring of length k, starting from 2 up to the length of the string: a. Determine the start and end indices of the substring. b. If the first and last characters of the substring are the same:
• Increment the length of the palindrome by 2, considering the characters at the remaining indices. c. If the first and last characters are different:
• Store the maximum length obtained by either excluding the last character or the first character.
5. The final value in the top-right corner of the matrix will represent the length of the longest palindromic subsequence.

## Example and Output:

Let's consider a few examples to demonstrate the algorithm's effectiveness:

1. Example A:

• Text: "pewmoozdp"
• Resultant Palindrome: "poop"
• Length: 4
2. Example B:

• Text: "xbfdsafx"
• Resultant Palindromes: "xfsfx", "xfdfx", "xfafx"
• Length: 5
3. Example C:

• Text: "abbisstiwebaccess"
• Resultant Palindrome: "abissiba"
• Length: 8

The time complexity of the given dynamic programming solution for finding the longest palindromic subsequence is O(n^2), where n is the length of the input string.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post