# Longest palindromic subsequence using dynamic programming

Here given code implementation process.

``````/*
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``````

## 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.