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)
    {
        Subsequence task = new Subsequence();
        String text1 = "pewmoozdp";
        String text2 = "xbfdsafx";
        String text3 = "abbisstiwebaccess";
        // Test A
        // Text = pewmoozdp
        // "poop" is resultant palindrome
        // Length 4
        int ans = task.findLPS(text1);
        System.out.print("\n Given : " + text1);
        System.out.print("\n Result : " + ans);
        // Test B
        // Text = xbfdsafx
        // [xfsfx,xfdfx,xfafx] is resultant palindrome
        // Length 5
        ans = task.findLPS(text2);
        System.out.print("\n Given : " + text2);
        System.out.print("\n Result : " + ans);
        // Test C
        // Text = "abbisstiwebaccess"
        // [abissiba] is resultant palindrome
        // Length 8
        ans = task.findLPS(text3);
        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()
{
    Subsequence *task = new Subsequence();
    string text1 = "pewmoozdp";
    string text2 = "xbfdsafx";
    string text3 = "abbisstiwebaccess";
    // Test A
    // Text = pewmoozdp
    // "poop" is resultant palindrome
    // Length 4
    int ans = task->findLPS(text1);
    cout << "\n Given : " << text1;
    cout << "\n Result : " << ans;
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    ans = task->findLPS(text2);
    cout << "\n Given : " << text2;
    cout << "\n Result : " << ans;
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    ans = task->findLPS(text3);
    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)
    {
        Subsequence task = new Subsequence();
        String text1 = "pewmoozdp";
        String text2 = "xbfdsafx";
        String text3 = "abbisstiwebaccess";
        // Test A
        // Text = pewmoozdp
        // "poop" is resultant palindrome
        // Length 4
        int ans = task.findLPS(text1);
        Console.Write("\n Given : " + text1);
        Console.Write("\n Result : " + ans);
        // Test B
        // Text = xbfdsafx
        // [xfsfx,xfdfx,xfafx] is resultant palindrome
        // Length 5
        ans = task.findLPS(text2);
        Console.Write("\n Given : " + text2);
        Console.Write("\n Result : " + ans);
        // Test C
        // Text = "abbisstiwebaccess"
        // [abissiba] is resultant palindrome
        // Length 8
        ans = task.findLPS(text3);
        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
    var ans int = task.findLPS(text1)
    fmt.Print("\n Given : ", text1)
    fmt.Print("\n Result : ", ans)
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    ans = task.findLPS(text2)
    fmt.Print("\n Given : ", text2)
    fmt.Print("\n Result : ", ans)
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    ans = task.findLPS(text3)
    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()
{
    $task = new Subsequence();
    $text1 = "pewmoozdp";
    $text2 = "xbfdsafx";
    $text3 = "abbisstiwebaccess";
    // Test A
    // Text = pewmoozdp
    // "poop" is resultant palindrome
    // Length 4
    $ans = $task->findLPS($text1);
    echo("\n Given : ".$text1);
    echo("\n Result : ".$ans);
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    $ans = $task->findLPS($text2);
    echo("\n Given : ".$text2);
    echo("\n Result : ".$ans);
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    $ans = $task->findLPS($text3);
    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 task = new Subsequence();
    var text1 = "pewmoozdp";
    var text2 = "xbfdsafx";
    var text3 = "abbisstiwebaccess";
    // Test A
    // Text = pewmoozdp
    // "poop" is resultant palindrome
    // Length 4
    var ans = task.findLPS(text1);
    process.stdout.write("\n Given : " + text1);
    process.stdout.write("\n Result : " + ans);
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    ans = task.findLPS(text2);
    process.stdout.write("\n Given : " + text2);
    process.stdout.write("\n Result : " + ans);
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    ans = task.findLPS(text3);
    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() :
    task = Subsequence()
    text1 = "pewmoozdp"
    text2 = "xbfdsafx"
    text3 = "abbisstiwebaccess"
    #  Test A
    #  Text = pewmoozdp
    #  "poop" is resultant palindrome
    #  Length 4
    ans = task.findLPS(text1)
    print("\n Given : ", text1, end = "")
    print("\n Result : ", ans, end = "")
    #  Test B
    #  Text = xbfdsafx
    #  [xfsfx,xfdfx,xfafx] is resultant palindrome
    #  Length 5
    ans = task.findLPS(text2)
    print("\n Given : ", text2, end = "")
    print("\n Result : ", ans, end = "")
    #  Test C
    #  Text = "abbisstiwebaccess"
    #  [abissiba] is resultant palindrome
    #  Length 8
    ans = task.findLPS(text3)
    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() 
    task = Subsequence.new()
    text1 = "pewmoozdp"
    text2 = "xbfdsafx"
    text3 = "abbisstiwebaccess"
    #  Test A
    #  Text = pewmoozdp
    #  "poop" is resultant palindrome
    #  Length 4
    ans = task.findLPS(text1)
    print("\n Given : ", text1)
    print("\n Result : ", ans)
    #  Test B
    #  Text = xbfdsafx
    #  [xfsfx,xfdfx,xfafx] is resultant palindrome
    #  Length 5
    ans = task.findLPS(text2)
    print("\n Given : ", text2)
    print("\n Result : ", ans)
    #  Test C
    #  Text = "abbisstiwebaccess"
    #  [abissiba] is resultant palindrome
    #  Length 8
    ans = task.findLPS(text3)
    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
        var ans: Int = task.findLPS(text1);
        print("\n Given : " + text1);
        print("\n Result : " + ans);
        // Test B
        // Text = xbfdsafx
        // [xfsfx,xfdfx,xfafx] is resultant palindrome
        // Length 5
        ans = task.findLPS(text2);
        print("\n Given : " + text2);
        print("\n Result : " + ans);
        // Test C
        // Text = "abbisstiwebaccess"
        // [abissiba] is resultant palindrome
        // Length 8
        ans = task.findLPS(text3);
        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 task: Subsequence = Subsequence();
    let text1: String = "pewmoozdp";
    let text2: String = "xbfdsafx";
    let text3: String = "abbisstiwebaccess";
    // Test A
    // Text = pewmoozdp
    // "poop" is resultant palindrome
    // Length 4
    var ans: Int = task.findLPS(text1);
    print("\n Given : ", text1, terminator: "");
    print("\n Result : ", ans, terminator: "");
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    ans = task.findLPS(text2);
    print("\n Given : ", text2, terminator: "");
    print("\n Result : ", ans, terminator: "");
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    ans = task.findLPS(text3);
    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 task: Subsequence = Subsequence();
    val text1: String = "pewmoozdp";
    val text2: String = "xbfdsafx";
    val text3: String = "abbisstiwebaccess";
    // Test A
    // Text = pewmoozdp
    // "poop" is resultant palindrome
    // Length 4
    var ans: Int = task.findLPS(text1);
    print("\n Given : " + text1);
    print("\n Result : " + ans);
    // Test B
    // Text = xbfdsafx
    // [xfsfx,xfdfx,xfafx] is resultant palindrome
    // Length 5
    ans = task.findLPS(text2);
    print("\n Given : " + text2);
    print("\n Result : " + ans);
    // Test C
    // Text = "abbisstiwebaccess"
    // [abissiba] is resultant palindrome
    // Length 8
    ans = task.findLPS(text3);
    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.

New Comment





Categories
Relative Post