Posted on by Kalkicode
Code Dynamic Programming

# Palindrome partition using dynamic programming

Palindrome partitioning is a dynamic programming problem that involves dividing a given string into the minimum number of substrings, where each substring is a palindrome. A palindrome is a sequence of characters that reads the same forwards as backwards. This problem finds applications in text processing, DNA sequence analysis, and optimization algorithms. In this article, we'll explore how to solve the palindrome partitioning problem using dynamic programming and provide clear explanations along with code examples.

## Problem Statement and Description

Given a string, the goal of palindrome partitioning is to determine the minimum number of partitions required to transform the entire string into palindromic substrings. The task is to find a partitioning that minimizes the number of cuts needed to achieve this transformation.

## Example

Consider the following examples to understand the concept:

• For the string "kdkrepaperspop": The optimal partitioning is "kdk | repaper | s | pop", resulting in three palindromic substrings. Hence, the minimum number of partitions is 3.

• For the string "civic": The string itself is a palindrome, so no partitioning is needed. The minimum number of partitions is 0.

• For the string "abcde": The optimal partitioning is "a | b | c | d | e", resulting in five substrings. Since each character forms a palindrome, the minimum number of partitions is equal to the length of the string.

## Idea to Solve the Problem

To solve the palindrome partitioning problem, we can use dynamic programming. The idea is to maintain a 2D table where each entry dp[i][j] represents whether the substring from index i to j is a palindrome. Using this table, we can calculate the minimum number of partitions required to make each substring palindrome.

## Standard Pseudocode

``````function palindromicPartition(text):
n = length of text
dp = 2D array of size (n+1) x (n+1)
partition = array of size n

initialize all entries of dp to 0
initialize all entries of partition to Integer.MAX_VALUE

for i from 0 to n:
dp[i][i] = 1

for i from 0 to n-1:
if text[i] == text[i+1]:
dp[i][i+1] = 1

for length from 3 to n:
for i from 0 to n-length+1:
j = i + length - 1
if text[i] == text[j] and dp[i+1][j-1] > 0:
dp[i][j] = 1

for i from 0 to n:
k = Integer.MAX_VALUE
if dp[0][i] > 0:
partition[i] = 0
else:
for j from 0 to i:
if dp[j+1][i] > 0 and k > partition[j] + 1:
k = partition[j] + 1
partition[i] = k

print "Given Text :", text
print "Partition  :", partition[n-1]``````

## Algorithm Explanation

1. Initialize a 2D array `dp` of size (n+1) x (n+1) to store whether substrings are palindromes.
2. Initialize an array `partition` of size n to store the minimum number of partitions for each substring.
3. Initialize all entries of `dp` and `partition` to appropriate initial values.
4. Mark single characters as palindromes (dp[i][i] = 1).
5. Check for adjacent characters that are the same and mark them as palindromes (dp[i][i+1] = 1).
6. For each length of substring from 3 to n, iterate through all possible substrings and check if the ends are equal and the inner substring is a palindrome.
7. Calculate the minimum number of partitions using the calculated palindromic information and store it in the `partition` array.
8. Print the original text and the minimum number of partitions.

## Code Solution

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

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

#### 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()
{
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
}
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()
{
// Test A
//  string = kdkrepaperspop
//  kdk repaper s pop
//     -       - -
//     ➀      ➁ ➂
//  3 partitions possible by max length
//  Result = 1
// Test B
//  string = civic
//  String is already palindrome so no partition
//  Result = 0
// Test C
//  string = abcde
//  a b c d e
//   - - - -
//  Result = 4
// Test D
//  string = axyiniol
//  a x y ini o l
//   - - -   - -
//  Result = 5
}
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() :
#  Test A
#   string = kdkrepaperspop
#   kdk repaper s pop
#      -       - -
#      ➀      ➁ ➂
#   3 partitions possible by max length
#   Result = 1
#  Test B
#   string = civic
#   String is already palindrome so no partition
#   Result = 0
#  Test C
#   string = abcde
#   a b c d e
#    - - - -
#   Result = 4
#  Test D
#   string = axyiniol
#   a x y ini o l
#    - - -   - -
#   Result = 5

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

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

#### Output

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

## Time Complexity

The time complexity of the provided algorithm is O(n^2), where n is the length of the input string. This is because the algorithm fills the `dp` table with O(n^2) entries. The space complexity is also O(n^2) due to the storage of the dynamic programming table.

## Comment

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

Categories
Relative Post