Posted on by Kalkicode
Code Dynamic Programming

Longest palindromic substring using dynamic programming

Dynamic programming is a technique used to solve complex problems by breaking them down into smaller overlapping subproblems and solving them independently. In this article, we will explore how dynamic programming can be used to find the longest palindromic substring in a given string. A palindromic substring is a substring that remains the same when read forwards or backwards.

Problem Statement

Given a string, we want to find the longest palindromic substring within that string. For example, in the string "nitiiiigi", the longest palindromic substring is "iiii", and in the string "vvvvivfvim", the longest palindromic substring is "ivfvi". Our task is to develop an algorithm using dynamic programming to efficiently solve this problem.

Pseudocode Algorithm with Explanation

Let's walk through the algorithm step by step:

1. Start by defining the function findLPS which takes a string called text as input.
2. Get the length of the input text and store it in the variable n.
3. If the length of the text is zero, return as there are no palindromic substrings to find.
4. Initialize variables length, start, and dp[n][n].
5. Initialize all elements of dp to 0 using nested for loops.
6. Set the diagonal elements of dp to 1 because a single character is always a palindrome.
7. Compare adjacent characters in the text using another for loop.
8. If two adjacent characters are the same, set dp[i][i+1] to 1, update the length to 2, and store the starting index in the variable start.
9. Iterate over k from 3 to n (length of text + 1).
10. Within the loop, use nested loops to iterate over all possible substrings of length k.
11. Check if the substring from i to j (i + k - 1) is a palindrome by verifying if dp[i + 1][j - 1] is 1 and text[i] is equal to text[j].
12. If the substring is a palindrome, set dp[i][j] to 1 and update the length and start variables if necessary.
13. After finding the longest palindromic substring, display the given text.
14. Print the resultant palindrome by iterating over the characters from start to start + length - 1.
15. Print the length of the resultant palindrome.
16. End the function.
17. In the main function, call findLPS with different test cases to demonstrate the algorithm's functionality.

Code Solution

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

void findLPS(char *text)
{
  // Get length of text
  int n = strlen(text);
  if (n == 0)
  {
    // When text is empty
    return;
  }
  int length = 1;
  int start = 0;
  int dp[n][n];
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      dp[i][j] = 0;
    }
  }
  // Set diagonal elements value is 1
  for (int i = 0; i < n; ++i)
  {
    dp[i][i] = 1;
  }
  // Compare adjacent character
  for (int i = 0; i < n - 1; ++i)
  {
    if (text[i] == text[i + 1])
    {
      // When adjacent elements is similar
      dp[i][i + 1] = 1;
      // Change resultant length
      length = 2;
      start = i;
    }
  }
  for (int k = 3; k <= n; ++k)
  {
    for (int i = 0; i < n - k + 1; ++i)
    {
      int j = i + k - 1;
      if (dp[i + 1][j - 1] && text[i] == text[j])
      {
        dp[i][j] = 1;
        if (k > length)
        {
          // Change resultant length
          length = k;
          // Update resultant starting location
          start = i;
        }
      }
    }
  }
  // Display given text
  printf("\n Given string : %s", text);
  printf("\n Result : ");
  // Display resultant palindrome
  for (int i = start; i <= start + length - 1; ++i)
  {
    printf("%c", text[i]);
  }
  // Display length of resultant palindrome
  printf("\n Resultant length : %d", length);
}
int main(int argc, char
  const *argv[])
{
  // Test
  // iiii => 4
  findLPS("nitiiiigi");
  // ivfvi => 5
  findLPS("vvvvivfvim");
  // civic => 5
  findLPS("xyzacivicxrs");
  // opo => 3
  findLPS("ttoopo");
  return 0;
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Java program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
    public void findLPS(String text)
    {
        // Get length of text
        int n = text.length();
        if (n == 0)
        {
            // When text is empty
            return;
        }
        int length = 1;
        int start = 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                dp[i][j] = 0;
            }
        }
        // Set diagonal elements value is 1
        for (int i = 0; i < n; ++i)
        {
            dp[i][i] = 1;
        }
        // Compare adjacent character
        for (int i = 0; i < n - 1; ++i)
        {
            if (text.charAt(i) == text.charAt(i + 1))
            {
                // When adjacent elements is similar
                dp[i][i + 1] = 1;
                // Change resultant length
                length = 2;
                start = i;
            }
        }
        for (int k = 3; k <= n; ++k)
        {
            for (int i = 0; i < n - k + 1; ++i)
            {
                int j = i + k - 1;
                if (dp[i + 1][j - 1] != 0 && text.charAt(i) == text.charAt(j))
                {
                    dp[i][j] = 1;
                    if (k > length)
                    {
                        // Change resultant length
                        length = k;
                        // Update resultant starting location
                        start = i;
                    }
                }
            }
        }
        // Display given text
        System.out.print("\n Given string : " + text);
        System.out.print("\n Result : ");
        // Display resultant palindrome
        for (int i = start; i <= start + length - 1; ++i)
        {
            System.out.print(text.charAt(i));
        }
        // Display length of resultant palindrome
        System.out.print("\n Resultant length : " + length);
    }
    public static void main(String[] args)
    {
        LongestPalindrome task = new LongestPalindrome();
        // Test
        // iiii => 4
        task.findLPS("nitiiiigi");
        // ivfvi => 5
        task.findLPS("vvvvivfvim");
        // civic => 5
        task.findLPS("xyzacivicxrs");
        // opo => 3
        task.findLPS("ttoopo");
    }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Include header file
#include <iostream>
#include <string>
using namespace std;

// C++ program for
// Longest palindromic substring using dynamic programming

class LongestPalindrome
{
  public: void findLPS(string text)
  {
    // Get length of text
    int n = text.length();
    if (n == 0)
    {
      // When text is empty
      return;
    }
    int length = 1;
    int start = 0;
    int dp[n][n];
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        dp[i][j] = 0;
      }
    }
    // Set diagonal elements value is 1
    for (int i = 0; i < n; ++i)
    {
      dp[i][i] = 1;
    }
    // Compare adjacent character
    for (int i = 0; i < n - 1; ++i)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (int k = 3; k <= n; ++k)
    {
      for (int i = 0; i < n - k + 1; ++i)
      {
        int j = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && text[i] == text[j])
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    cout << "\n Given string : " << text;
    cout << "\n Result : ";
    // Display resultant palindrome
    for (int i = start; i <= start + length - 1; ++i)
    {
      cout << text[i];
    }
    // Display length of resultant palindrome
    cout << "\n Resultant length : " << length;
  }
};
int main()
{
  LongestPalindrome *task = new LongestPalindrome();
  // Test
  // iiii => 4
  task->findLPS("nitiiiigi");
  // ivfvi => 5
  task->findLPS("vvvvivfvim");
  // civic => 5
  task->findLPS("xyzacivicxrs");
  // opo => 3
  task->findLPS("ttoopo");
  return 0;
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Include namespace system
using System;
// Csharp program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
  public void findLPS(String text)
  {
    // Get length of text
    int n = text.Length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    int length = 1;
    int start = 0;
    int[,] dp = new int[n,n];
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        dp[i,j] = 0;
      }
    }
    // Set diagonal elements value is 1
    for (int i = 0; i < n; ++i)
    {
      dp[i,i] = 1;
    }
    // Compare adjacent character
    for (int i = 0; i < n - 1; ++i)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i,i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (int k = 3; k <= n; ++k)
    {
      for (int i = 0; i < n - k + 1; ++i)
      {
        int j = i + k - 1;
        if (dp[i + 1,j - 1] != 0 && text[i] == text[j])
        {
          dp[i,j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    Console.Write("\n Given string : " + text);
    Console.Write("\n Result : ");
    // Display resultant palindrome
    for (int i = start; i <= start + length - 1; ++i)
    {
      Console.Write(text[i]);
    }
    // Display length of resultant palindrome
    Console.Write("\n Resultant length : " + length);
  }
  public static void Main(String[] args)
  {
    LongestPalindrome task = new LongestPalindrome();
    // Test
    // iiii => 4
    task.findLPS("nitiiiigi");
    // ivfvi => 5
    task.findLPS("vvvvivfvim");
    // civic => 5
    task.findLPS("xyzacivicxrs");
    // opo => 3
    task.findLPS("ttoopo");
  }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
package main
import "fmt"
// Go program for
// Longest palindromic substring using dynamic programming

func findLPS(text string) {
  // Get length of text
  var n int = len(text)
  if n == 0 {
    // When text is empty
    return
  }
  var length int = 1
  var start int = 0
  var dp = make([][] int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int,n)
  }
  // Set diagonal elements value is 1
  for i := 0 ; i < n ; i++ {
    dp[i][i] = 1
  }
  // Compare adjacent character
  for i := 0 ; i < n - 1 ; i++ {
    if text[i] == text[i + 1] {
      // When adjacent elements is similar
      dp[i][i + 1] = 1
      // Change resultant length
      length = 2
      start = i
    }
  }
  for k := 3 ; k <= n ; k++ {
    for i := 0 ; i < n - k + 1 ; i++ {
      var j int = i + k - 1
      if dp[i + 1][j - 1] != 0 && text[i] == text[j] {
        dp[i][j] = 1
        if k > length {
          // Change resultant length
          length = k
          // Update resultant starting location
          start = i
        }
      }
    }
  }
  // Display given text
  fmt.Print("\n Given string : ", text)
  fmt.Print("\n Result : ")
  // Display resultant palindrome
  for i := start ; i <= start + length - 1 ; i++ {
    fmt.Print(string(text[i]))
  }
  // Display length of resultant palindrome
  fmt.Print("\n Resultant length : ", length)
}
func main() {
  
  // Test
  // iiii => 4
  findLPS("nitiiiigi")
  // ivfvi => 5
  findLPS("vvvvivfvim")
  // civic => 5
  findLPS("xyzacivicxrs")
  // opo => 3
  findLPS("ttoopo")
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
<?php
// Php program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  public  function findLPS($text)
  {
    // Get length of text
    $n = strlen($text);
    if ($n == 0)
    {
      // When text is empty
      return;
    }
    $length = 1;
    $start = 0;
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    // Set diagonal elements value is 1
    for ($i = 0; $i < $n; ++$i)
    {
      $dp[$i][$i] = 1;
    }
    // Compare adjacent character
    for ($i = 0; $i < $n - 1; ++$i)
    {
      if ($text[$i] == $text[$i + 1])
      {
        // When adjacent elements is similar
        $dp[$i][$i + 1] = 1;
        // Change resultant length
        $length = 2;
        $start = $i;
      }
    }
    for ($k = 3; $k <= $n; ++$k)
    {
      for ($i = 0; $i < $n - $k + 1; ++$i)
      {
        $j = $i + $k - 1;
        if ($dp[$i + 1][$j - 1] != 0 && $text[$i] == $text[$j])
        {
          $dp[$i][$j] = 1;
          if ($k > $length)
          {
            // Change resultant length
            $length = $k;
            // Update resultant starting location
            $start = $i;
          }
        }
      }
    }
    // Display given text
    echo("\n Given string : ".$text);
    echo("\n Result : ");
    // Display resultant palindrome
    for ($i = $start; $i <= $start + $length - 1; ++$i)
    {
      echo($text[$i]);
    }
    // Display length of resultant palindrome
    echo("\n Resultant length : ".$length);
  }
}

function main()
{
  $task = new LongestPalindrome();
  // Test
  // iiii => 4
  $task->findLPS("nitiiiigi");
  // ivfvi => 5
  $task->findLPS("vvvvivfvim");
  // civic => 5
  $task->findLPS("xyzacivicxrs");
  // opo => 3
  $task->findLPS("ttoopo");
}
main();

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Node JS program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  findLPS(text)
  {
    // Get length of text
    var n = text.length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length = 1;
    var start = 0;
    var dp = Array(n).fill(0).map(() => new Array(n).fill(0));
    // Set diagonal elements value is 1
    for (var i = 0; i < n; ++i)
    {
      dp[i][i] = 1;
    }
    // Compare adjacent character
    for (var i = 0; i < n - 1; ++i)
    {
      if (text.charAt(i) == text.charAt(i + 1))
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (var k = 3; k <= n; ++k)
    {
      for (var i = 0; i < n - k + 1; ++i)
      {
        var j = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && 
                    text.charAt(i) == text.charAt(j))
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    process.stdout.write("\n Given string : " + text);
    process.stdout.write("\n Result : ");
    // Display resultant palindrome
    for (var i = start; i <= start + length - 1; ++i)
    {
      process.stdout.write(text.charAt(i));
    }
    // Display length of resultant palindrome
    process.stdout.write("\n Resultant length : " + length);
  }
}

function main()
{
  var task = new LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}
main();

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
#  Python 3 program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome :
  def findLPS(self, text) :
    #  Get length of text
    n = len(text)
    if (n == 0) :
      #  When text is empty
      return
    
    length = 1
    start = 0
    dp = [[0] * (n) for _ in range(n) ]
    i = 0
    #  Set diagonal elements value is 1
    while (i < n) :
      dp[i][i] = 1
      i += 1
    
    i = 0
    #  Compare adjacent character
    while (i < n - 1) :
      if (text[i] == text[i + 1]) :
        #  When adjacent elements is similar
        dp[i][i + 1] = 1
        #  Change resultant length
        length = 2
        start = i
      
      i += 1
    
    k = 3
    while (k <= n) :
      i = 0
      while (i < n - k + 1) :
        j = i + k - 1
        if (dp[i + 1][j - 1] != 0 and text[i] == text[j]) :
          dp[i][j] = 1
          if (k > length) :
            #  Change resultant length
            length = k
            #  Update resultant starting location
            start = i
          
        
        i += 1
      
      k += 1
    
    #  Display given text
    print("\n Given string : ", text, end = "")
    print("\n Result : ", end = "")
    i = start
    #  Display resultant palindrome
    while (i <= start + length - 1) :
      print(text[i], end = "")
      i += 1
    
    #  Display length of resultant palindrome
    print("\n Resultant length : ", length, end = "")
  

def main() :
  task = LongestPalindrome()
  #  Test
  #  iiii => 4
  task.findLPS("nitiiiigi")
  #  ivfvi => 5
  task.findLPS("vvvvivfvim")
  #  civic => 5
  task.findLPS("xyzacivicxrs")
  #  opo => 3
  task.findLPS("ttoopo")

if __name__ == "__main__": main()

Output

 Given string :  nitiiiigi
 Result : iiii
 Resultant length :  4
 Given string :  vvvvivfvim
 Result : ivfvi
 Resultant length :  5
 Given string :  xyzacivicxrs
 Result : civic
 Resultant length :  5
 Given string :  ttoopo
 Result : opo
 Resultant length :  3
#  Ruby program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome 
  def findLPS(text) 
    #  Get length of text
    n = text.length
    if (n == 0) 
      #  When text is empty
      return
    end

    length = 1
    start = 0
    dp = Array.new(n) {Array.new(n) {0}}
    i = 0
    #  Set diagonal elements value is 1
    while (i < n) 
      dp[i][i] = 1
      i += 1
    end

    i = 0
    #  Compare adjacent character
    while (i < n - 1) 
      if (text[i] == text[i + 1]) 
        #  When adjacent elements is similar
        dp[i][i + 1] = 1
        #  Change resultant length
        length = 2
        start = i
      end

      i += 1
    end

    k = 3
    while (k <= n) 
      i = 0
      while (i < n - k + 1) 
        j = i + k - 1
        if (dp[i + 1][j - 1] != 0 && text[i] == text[j]) 
          dp[i][j] = 1
          if (k > length) 
            #  Change resultant length
            length = k
            #  Update resultant starting location
            start = i
          end

        end

        i += 1
      end

      k += 1
    end

    #  Display given text
    print("\n Given string : ", text)
    print("\n Result : ")
    i = start
    #  Display resultant palindrome
    while (i <= start + length - 1) 
      print(text[i])
      i += 1
    end

    #  Display length of resultant palindrome
    print("\n Resultant length : ", length)
  end

end

def main() 
  task = LongestPalindrome.new()
  #  Test
  #  iiii => 4
  task.findLPS("nitiiiigi")
  #  ivfvi => 5
  task.findLPS("vvvvivfvim")
  #  civic => 5
  task.findLPS("xyzacivicxrs")
  #  opo => 3
  task.findLPS("ttoopo")
end

main()

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Scala program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome()
{
  def findLPS(text: String): Unit = {
    // Get length of text
    var n: Int = text.length();
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    var dp: Array[Array[Int]] = Array.fill[Int](n, n)(0);
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp(i)(i) = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text.charAt(i) == text.charAt(i + 1))
      {
        // When adjacent elements is similar
        dp(i)(i + 1) = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        var j: Int = i + k - 1;
        if (dp(i + 1)(j - 1) != 0 && 
                    text.charAt(i) == text.charAt(j))
        {
          dp(i)(j) = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : " + text);
    print("\n Result : ");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text.charAt(i));
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : " + length);
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var task: LongestPalindrome = new LongestPalindrome();
    // Test
    // iiii => 4
    task.findLPS("nitiiiigi");
    // ivfvi => 5
    task.findLPS("vvvvivfvim");
    // civic => 5
    task.findLPS("xyzacivicxrs");
    // opo => 3
    task.findLPS("ttoopo");
  }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
import Foundation;
// Swift 4 program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  func findLPS(_ data: String)
  {
        let text = Array(data);
    // Get length of text
    let n: Int = text.count;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: n), count: n);
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp[i][i] = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        let j: Int = i + k - 1;
        if (dp[i + 1][j - 1]  != 0 && text[i] == text[j])
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : ", data, terminator: "");
    print("\n Result : ", terminator: "");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text[i], terminator: "");
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : ", length, terminator: "");
  }
}
func main()
{
  let task: LongestPalindrome = LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}
main();

Output

 Given string :  nitiiiigi
 Result : iiii
 Resultant length :  4
 Given string :  vvvvivfvim
 Result : ivfvi
 Resultant length :  5
 Given string :  xyzacivicxrs
 Result : civic
 Resultant length :  5
 Given string :  ttoopo
 Result : opo
 Resultant length :  3
// Kotlin program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  fun findLPS(text: String): Unit
  {
    // Get length of text
    val n: Int = text.length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    val dp: Array < Array < Int >> = Array(n)
    {
      Array(n)
      {
        0
      }
    };
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp[i][i] = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text.get(i) == text.get(i + 1))
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        val j: Int = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && text.get(i) == text.get(j))
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : " + text);
    print("\n Result : ");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text.get(i));
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : " + length);
  }
}
fun main(args: Array < String > ): Unit
{
  val task: LongestPalindrome = LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3

Resultant Output Explanation

Let's understand the output generated by the code for the given test cases:

Given string : nitiiiigi
Result : iiii
Resultant length : 4

Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5

Given string : xyzacivicxrs
Result : civic
Resultant length : 5

Given string : ttoopo
Result : opo
Resultant length : 3

In the first test case, the input string "nitiiiigi" contains the longest palindromic substring "iiii", which has a length of 4. The second test case "vvvvivfvim" has "ivfvi" as the longest palindromic substring with a length of 5. Similarly, the third test case "xyzacivicxrs" has "civic" as the longest palindromic substring with a length of 5. Finally, in the fourth test case "ttoopo", the longest palindromic substring is "opo" with a length of 3.

Time Complexity

The time complexity of the dynamic programming solution to find the longest palindromic substring is O(n^2), where n is the length of the input string. This is because we iterate over all substrings of lengths ranging from 3 to n and compare characters within each substring. The nested loops and comparisons contribute to the quadratic time complexity.

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