# Palindrome partition using dynamic programming

Here given code implementation process.

``````/*
Java Program for
Palindrome partition using dynamic programming
*/
public class Palindrome
{
public void palindromicPartition(String text)
{
int n = text.length();
if (n == 0)
{
return;
}
int k = 0;
int[][] dp = new int[n + 1][n + 1];
int[] partition = new int[n];
// Set initial value of dp
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp[i][j] = 0;
}
}
// Set initial value of partition array
for (int i = 0; i < n; ++i)
{
partition[i] = Integer.MAX_VALUE;
}
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
// Calculate palindrome in consecutive substring length of 2
for (int i = 0; i < n - 1; i++)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When consecutive elements is same
dp[i][i + 1] = 1;
}
}
// Calculate palindrome in length greater than 2
for (int i = 3; i <= n; ++i)
{
for (int j = 0; j < n - i + 1; ++j)
{
k = j + i - 1;
if (text.charAt(j) == text.charAt(k))
{
if (dp[j + 1][k - 1] > 0)
{
dp[j][k] = 1;
}
}
}
}
for (int i = 0; i < n; ++i)
{
k = Integer.MAX_VALUE;
if (dp[0][i] > 0)
{
partition[i] = 0;
}
else
{
for (int j = 0; j < i; j++)
{
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
}
partition[i] = k;
}
}
System.out.println(" Given Text : " + text);
// Display calculated result
System.out.println(" Partition  : " + partition[n - 1]);
}
public static void main(String[] args)
{
Palindrome task = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````// Include header file
#include <iostream>
#include <string>
#include <limits.h>

using namespace std;
/*
C++ Program for
Palindrome partition using dynamic programming
*/
class Palindrome
{
public: void palindromicPartition(string text)
{
int n = text.length();
if (n == 0)
{
return;
}
int k = 0;
int dp[n + 1][n + 1];
int partition[n];
// Set initial value of dp
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp[i][j] = 0;
}
}
// Set initial value of partition array
for (int i = 0; i < n; ++i)
{
partition[i] = INT_MAX;
}
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
// Calculate palindrome in consecutive substring length of 2
for (int i = 0; i < n - 1; i++)
{
if (text[i] == text[i + 1])
{
// When consecutive elements is same
dp[i][i + 1] = 1;
}
}
// Calculate palindrome in length greater than 2
for (int i = 3; i <= n; ++i)
{
for (int j = 0; j < n - i + 1; ++j)
{
k = j + i - 1;
if (text[j] == text[k])
{
if (dp[j + 1][k - 1] > 0)
{
dp[j][k] = 1;
}
}
}
}
for (int i = 0; i < n; ++i)
{
k = INT_MAX;
if (dp[0][i] > 0)
{
partition[i] = 0;
}
else
{
for (int j = 0; j < i; j++)
{
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
}
partition[i] = k;
}
}
cout << " Given Text : " << text << endl;
// Display calculated result
cout << " Partition  : " << partition[n - 1] << endl;
}
};
int main()
{
Palindrome *task = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task->palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task->palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task->palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task->palindromicPartition("axyiniol");
return 0;
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````// Include namespace system
using System;
/*
Csharp Program for
Palindrome partition using dynamic programming
*/
public class Palindrome
{
public void palindromicPartition(String text)
{
int n = text.Length;
if (n == 0)
{
return;
}
int k = 0;
int[,] dp = new int[n + 1,n + 1];
int[] partition = new int[n];
// Set initial value of dp
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp[i,j] = 0;
}
}
// Set initial value of partition array
for (int i = 0; i < n; ++i)
{
partition[i] = int.MaxValue;
}
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for (int i = 0; i < n; ++i)
{
dp[i,i] = 1;
}
// Calculate palindrome in consecutive substring length of 2
for (int i = 0; i < n - 1; i++)
{
if (text[i] == text[i + 1])
{
// When consecutive elements is same
dp[i,i + 1] = 1;
}
}
// Calculate palindrome in length greater than 2
for (int i = 3; i <= n; ++i)
{
for (int j = 0; j < n - i + 1; ++j)
{
k = j + i - 1;
if (text[j] == text[k])
{
if (dp[j + 1,k - 1] > 0)
{
dp[j,k] = 1;
}
}
}
}
for (int i = 0; i < n; ++i)
{
k = int.MaxValue;
if (dp[0,i] > 0)
{
partition[i] = 0;
}
else
{
for (int j = 0; j < i; j++)
{
if ((dp[j + 1,i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
}
partition[i] = k;
}
}
Console.WriteLine(" Given Text : " + text);
// Display calculated result
Console.WriteLine(" Partition  : " + partition[n - 1]);
}
public static void Main(String[] args)
{
Palindrome task = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````package main
import "math"
import "fmt"
/*
Go Program for
Palindrome partition using dynamic programming
*/

func palindromicPartition(text string) {
var n int = len(text)
if n == 0 {
return
}
var k int = 0
// Set initial value of dp
var dp = make([][] int, n + 1)
for i := 0; i < n + 1; i++ {
dp[i] = make([] int, n + 1)
}
var partition = make([] int, n)
// Set initial value of partition array
for i := 0 ; i < n ; i++ {
partition[i] = math.MaxInt64
}
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for i := 0 ; i < n ; i++ {
dp[i][i] = 1
}
// Calculate palindrome in consecutive substring length of 2
for i := 0 ; i < n - 1 ; i++ {
if text[i] == text[i + 1] {
// When consecutive elements is same
dp[i][i + 1] = 1
}
}
// Calculate palindrome in length greater than 2
for i := 3 ; i <= n ; i++ {
for j := 0 ; j < n - i + 1 ; j++ {
k = j + i - 1
if text[j] == text[k] {
if dp[j + 1][k - 1] > 0 {
dp[j][k] = 1
}
}
}
}
for i := 0 ; i < n ; i++ {
k = math.MaxInt64
if dp[0][i] > 0 {
partition[i] = 0
} else {
for j := 0 ; j < i ; j++ {
if (dp[j + 1][i] > 0) && k > partition[j] + 1 {
// When substring is palindrome
k = partition[j] + 1
}
}
partition[i] = k
}
}
fmt.Println(" Given Text : ", text)
// Display calculated result
fmt.Println(" Partition  : ", partition[n - 1])
}
func main() {

// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
palindromicPartition("kdkrepaperspop")
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
palindromicPartition("civic")
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
palindromicPartition("abcde")
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
palindromicPartition("axyiniol")
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````<?php
/*
Php Program for
Palindrome partition using dynamic programming
*/
class Palindrome
{
public	function palindromicPartition(\$text)
{
\$n = strlen(\$text);
if (\$n == 0)
{
return;
}
\$k = 0;
// Set initial value of dp
\$dp = array_fill(0, \$n + 1, array_fill(0, \$n + 1, 0));
// Set initial value of partition array us PHP_INT_MAX
\$partition = array_fill(0, \$n, PHP_INT_MAX);

// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for (\$i = 0; \$i < \$n; ++\$i)
{
\$dp[\$i][\$i] = 1;
}
// Calculate palindrome in consecutive substring length of 2
for (\$i = 0; \$i < \$n - 1; \$i++)
{
if (\$text[\$i] == \$text[\$i + 1])
{
// When consecutive elements is same
\$dp[\$i][\$i + 1] = 1;
}
}
// Calculate palindrome in length greater than 2
for (\$i = 3; \$i <= \$n; ++\$i)
{
for (\$j = 0; \$j < \$n - \$i + 1; ++\$j)
{
\$k = \$j + \$i - 1;
if (\$text[\$j] == \$text[\$k])
{
if (\$dp[\$j + 1][\$k - 1] > 0)
{
\$dp[\$j][\$k] = 1;
}
}
}
}
for (\$i = 0; \$i < \$n; ++\$i)
{
\$k = PHP_INT_MAX;
if (\$dp[0][\$i] > 0)
{
\$partition[\$i] = 0;
}
else
{
for (\$j = 0; \$j < \$i; \$j++)
{
if ((\$dp[\$j + 1][\$i] > 0) && \$k > \$partition[\$j] + 1)
{
// When substring is palindrome
\$k = \$partition[\$j] + 1;
}
}
\$partition[\$i] = \$k;
}
}
echo(" Given Text : ".\$text."\n");
// Display calculated result
echo(" Partition  : ".\$partition[\$n - 1]."\n");
}
}

function main()
{
\$task = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
\$task->palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
\$task->palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
\$task->palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
\$task->palindromicPartition("axyiniol");
}
main();``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````/*
Node JS Program for
Palindrome partition using dynamic programming
*/
class Palindrome
{
palindromicPartition(text)
{
var n = text.length;
if (n == 0)
{
return;
}
var k = 0;
// Set initial value of dp
var dp = Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
var partition = Array(n).fill(Number.MAX_VALUE);

// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
for (var i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
// Calculate palindrome in consecutive substring length of 2
for (var i = 0; i < n - 1; i++)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When consecutive elements is same
dp[i][i + 1] = 1;
}
}
// Calculate palindrome in length greater than 2
for (var i = 3; i <= n; ++i)
{
for (var j = 0; j < n - i + 1; ++j)
{
k = j + i - 1;
if (text.charAt(j) == text.charAt(k))
{
if (dp[j + 1][k - 1] > 0)
{
dp[j][k] = 1;
}
}
}
}
for (var i = 0; i < n; ++i)
{
k = Number.MAX_VALUE;
if (dp[0][i] > 0)
{
partition[i] = 0;
}
else
{
for (var j = 0; j < i; j++)
{
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
}
partition[i] = k;
}
}
console.log(" Given Text : " + text);
// Display calculated result
console.log(" Partition  : " + partition[n - 1]);
}
}

function main()
{
var task = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}
main();``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````import sys
#    Python 3 Program for
#    Palindrome partition using dynamic programming
class Palindrome :
def palindromicPartition(self, text) :
n = len(text)
if (n == 0) :
return

k = 0
#  Set initial value of dp
dp = [[0] * (n + 1) for _ in range(n + 1) ]
partition = [sys.maxsize] * (n)

i = 0
#  Set diagonal elements is to 1.
#  1 indicates palindromic length of each character.
while (i < n) :
dp[i][i] = 1
i += 1

i = 0
#  Calculate palindrome in consecutive substring length of 2
while (i < n - 1) :
if (text[i] == text[i + 1]) :
#  When consecutive elements is same
dp[i][i + 1] = 1

i += 1

i = 3
#  Calculate palindrome in length greater than 2
while (i <= n) :
j = 0
while (j < n - i + 1) :
k = j + i - 1
if (text[j] == text[k]) :
if (dp[j + 1][k - 1] > 0) :
dp[j][k] = 1

j += 1

i += 1

i = 0
while (i < n) :
k = sys.maxsize
if (dp[0][i] > 0) :
partition[i] = 0
else :
j = 0
while (j < i) :
if ((dp[j + 1][i] > 0) and k > partition[j] + 1) :
#  When substring is palindrome
k = partition[j] + 1

j += 1

partition[i] = k

i += 1

print(" Given Text : ", text)
#  Display calculated result
print(" Partition  : ", partition[n - 1])

def main() :
task = Palindrome()
#  Test A
#   string = kdkrepaperspop
#   kdk repaper s pop
#      -       - -
#      ➀      ➁ ➂
#   3 partitions possible by max length
#   Result = 1
task.palindromicPartition("kdkrepaperspop")
#  Test B
#   string = civic
#   String is already palindrome so no partition
#   Result = 0
task.palindromicPartition("civic")
#  Test C
#   string = abcde
#   a b c d e
#    - - - -
#   Result = 4
task.palindromicPartition("abcde")
#  Test D
#   string = axyiniol
#   a x y ini o l
#    - - -   - -
#   Result = 5
task.palindromicPartition("axyiniol")

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

#### Output

`````` Given Text :  kdkrepaperspop
Partition  :  3
Given Text :  civic
Partition  :  0
Given Text :  abcde
Partition  :  4
Given Text :  axyiniol
Partition  :  5``````
``````#    Ruby Program for
#    Palindrome partition using dynamic programming
class Palindrome
def palindromicPartition(text)
n = text.length
if (n == 0)
return
end

k = 0
#  Set initial value of dp
dp = Array.new(n + 1) {Array.new(n + 1) {0}}
partition = Array.new(n) {(2 ** (0.size * 8 - 2))}

i = 0
#  Set diagonal elements is to 1.
#  1 indicates palindromic length of each character.
while (i < n)
dp[i][i] = 1
i += 1
end

i = 0
#  Calculate palindrome in consecutive substring length of 2
while (i < n - 1)
if (text[i] == text[i + 1])
#  When consecutive elements is same
dp[i][i + 1] = 1
end

i += 1
end

i = 3
#  Calculate palindrome in length greater than 2
while (i <= n)
j = 0
while (j < n - i + 1)
k = j + i - 1
if (text[j] == text[k])
if (dp[j + 1][k - 1] > 0)
dp[j][k] = 1
end

end

j += 1
end

i += 1
end

i = 0
while (i < n)
k = (2 ** (0. size * 8 - 2))
if (dp[0][i] > 0)
partition[i] = 0
else

j = 0
while (j < i)
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
#  When substring is palindrome
k = partition[j] + 1
end

j += 1
end

partition[i] = k
end

i += 1
end

print(" Given Text : ", text, "\n")
#  Display calculated result
print(" Partition  : ", partition[n - 1], "\n")
end

end

def main()
task = Palindrome.new()
#  Test A
#   string = kdkrepaperspop
#   kdk repaper s pop
#      -       - -
#      ➀      ➁ ➂
#   3 partitions possible by max length
#   Result = 1
task.palindromicPartition("kdkrepaperspop")
#  Test B
#   string = civic
#   String is already palindrome so no partition
#   Result = 0
task.palindromicPartition("civic")
#  Test C
#   string = abcde
#   a b c d e
#    - - - -
#   Result = 4
task.palindromicPartition("abcde")
#  Test D
#   string = axyiniol
#   a x y ini o l
#    - - -   - -
#   Result = 5
task.palindromicPartition("axyiniol")
end

main()``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5
``````
``````import scala.collection.mutable._;
/*
Scala Program for
Palindrome partition using dynamic programming
*/
class Palindrome()
{
def palindromicPartition(text: String): Unit = {
var n: Int = text.length();
if (n == 0)
{
return;
}
var k: Int = 0;
// Set initial value of dp
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, n + 1)(0);
var partition: Array[Int] = Array.fill[Int](n)(Int.MaxValue);
var i: Int = 0;
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
while (i < n)
{
dp(i)(i) = 1;
i += 1;
}
i = 0;
// Calculate palindrome in consecutive substring length of 2
while (i < n - 1)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When consecutive elements is same
dp(i)(i + 1) = 1;
}
i += 1;
}
i = 3;
// Calculate palindrome in length greater than 2
while (i <= n)
{
var j: Int = 0;
while (j < n - i + 1)
{
k = j + i - 1;
if (text.charAt(j) == text.charAt(k))
{
if (dp(j + 1)(k - 1) > 0)
{
dp(j)(k) = 1;
}
}
j += 1;
}
i += 1;
}
i = 0;
while (i < n)
{
k = Int.MaxValue;
if (dp(0)(i) > 0)
{
partition(i) = 0;
}
else
{
var j: Int = 0;
while (j < i)
{
if ((dp(j + 1)(i) > 0) && k > partition(j) + 1)
{
// When substring is palindrome
k = partition(j) + 1;
}
j += 1;
}
partition(i) = k;
}
i += 1;
}
println(" Given Text : " + text);
// Display calculated result
println(" Partition  : " + partition(n - 1));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Palindrome = new Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````
``````/*
Swift 4 Program for
Palindrome partition using dynamic programming
*/
class Palindrome
{
func palindromicPartition(_ data: String)
{
let text = Array(data);
let n: Int = text.count;
if (n == 0)
{
return;
}
var k: Int = 0;
// Set initial value of dp
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1);
var partition: [Int] = Array(repeating: Int.max, count: n);

var i: Int = 0;
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
i = 0;
// Calculate palindrome in consecutive substring length of 2
while (i < n - 1)
{
if (text[i] == text[i + 1])
{
// When consecutive elements is same
dp[i][i + 1] = 1;
}
i += 1;
}
i = 3;
// Calculate palindrome in length greater than 2
while (i <= n)
{
var j: Int = 0;
while (j < n - i + 1)
{
k = j + i - 1;
if (text[j] == text[k])
{
if (dp[j + 1][k - 1] > 0)
{
dp[j][k] = 1;
}
}
j += 1;
}
i += 1;
}
i = 0;
while (i < n)
{
k = Int.max;
if (dp[0][i] > 0)
{
partition[i] = 0;
}
else
{
var j: Int = 0;
while (j < i)
{
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
j += 1;
}
partition[i] = k;
}
i += 1;
}
print(" Given Text : ", data);
// Display calculated result
print(" Partition  : ", partition[n - 1]);
}
}
func main()
{
let task: Palindrome = Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}
main();``````

#### Output

`````` Given Text :  kdkrepaperspop
Partition  :  3
Given Text :  civic
Partition  :  0
Given Text :  abcde
Partition  :  4
Given Text :  axyiniol
Partition  :  5``````
``````/*
Kotlin Program for
Palindrome partition using dynamic programming
*/
class Palindrome
{
fun palindromicPartition(text: String): Unit
{
val n: Int = text.length;
if (n == 0)
{
return;
}
var k: Int ;
// Set initial value of dp
val dp: Array < Array < Int >> = Array(n + 1)
{
Array(n + 1)
{
0
}
};
val partition: Array < Int > = Array(n)
{
Int.MAX_VALUE
};

var i = 0;
// Set diagonal elements is to 1.
// 1 indicates palindromic length of each character.
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
i = 0;
// Calculate palindrome in consecutive substring length of 2
while (i < n - 1)
{
if (text.get(i) == text.get(i + 1))
{
// When consecutive elements is same
dp[i][i + 1] = 1;
}
i += 1;
}
i = 3;
// Calculate palindrome in length greater than 2
while (i <= n)
{
var j: Int = 0;
while (j < n - i + 1)
{
k = j + i - 1;
if (text.get(j) == text.get(k))
{
if (dp[j + 1][k - 1] > 0)
{
dp[j][k] = 1;
}
}
j += 1;
}
i += 1;
}
i = 0;
while (i < n)
{
k = Int.MAX_VALUE;
if (dp[0][i] > 0)
{
partition[i] = 0;
}
else
{
var j: Int = 0;
while (j < i)
{
if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
{
// When substring is palindrome
k = partition[j] + 1;
}
j += 1;
}
partition[i] = k;
}
i += 1;
}
println(" Given Text : " + text);
// Display calculated result
println(" Partition  : " + partition[n - 1]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Palindrome = Palindrome();
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
task.palindromicPartition("kdkrepaperspop");
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
task.palindromicPartition("civic");
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
task.palindromicPartition("abcde");
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
task.palindromicPartition("axyiniol");
}``````

#### Output

`````` Given Text : kdkrepaperspop
Partition  : 3
Given Text : civic
Partition  : 0
Given Text : abcde
Partition  : 4
Given Text : axyiniol
Partition  : 5``````

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

© 2022, kalkicode.com, All rights reserved