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)
	{
		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

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.

New Comment