Skip to main content

Print all palindromic partitions of a string

A palindromic partition of a string is a way to break up the string into substrings such that each substring is a palindrome, meaning it reads the same backward as forward. For example, the palindromic partitions of the string "minimum" are.

m  i  n  i  m  u  m
m  i  n  i  mum
m  ini  m  u  m
m  ini  mum
minim  u  m

Code Solution

import java.util.ArrayList;
/*
    Java program
    Print all palindromic partitions of a string
*/
public class Partition
{
	// Check that given substring is palindrome or not
	public boolean isPalindrome(String text, int first, int last)
	{
		while (first < last)
		{
			if (text.charAt(first) != text.charAt(last))
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first++;
			last--;
		}
		return true;
	}
	// Find all palindromic substring in given text
	public void palindromicPart(ArrayList < ArrayList < String >> record, 
                                ArrayList < String > track, 
                                 int start, int n, String text)
	{
		if (start >= n)
		{
			record.add(new ArrayList < String > (track));
		}
		else
		{
			for (int i = start; i < n; i++)
			{
				if (isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track.add(text.substring(start, i + 1));
					palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.remove(track.size() - 1);
				}
			}
		}
	}
	public void palindromicSplit(String text)
	{
		int n = text.length();
		ArrayList < ArrayList < String >> record = 
                                          new ArrayList < ArrayList < String >> ();
		ArrayList < String > track = new ArrayList < String > ();
		palindromicPart(record, track, 0, n, text);
		// Display calculated palindromic substring
		for (int i = 0; i < record.size(); ++i)
		{
			for (int j = 0; j < record.get(i).size(); ++j)
			{
				System.out.print("  " + record.get(i).get(j));
			}
			System.out.print("\n");
		}
	}
	public static void main(String[] args)
	{
		Partition task = new Partition();
		String text = "minimum";
		// All palindromic substring
		task.palindromicSplit(text);
	}
}

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
// Include header file
#include <iostream>
#include <string>
#include <vector>

using namespace std;
/*
    C++ program
    Print all palindromic partitions of a string
*/
class Partition
{
	public:
		// Check that given substring is palindrome or not
		bool isPalindrome(string text, int first, int last)
		{
			while (first < last)
			{
				if (text[first] != text[last])
				{
					// When boundary characters are different
					return false;
				}
				// Change element position
				first++;
				last--;
			}
			return true;
		}
	// Find all palindromic substring in given text
	void palindromicPart(vector < vector < string > > &record, 
                         vector < string > track, 
                         int start, int n, string text)
	{
		if (start >= n)
		{
			record.push_back(track);
		}
		else
		{
			for (int i = start; i < n; i++)
			{
				if (this->isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track.push_back(text.substr(start, i-start+1));
					this->palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.pop_back();
				}
			}
		}
	}
	void palindromicSplit(string text)
	{
		int n = text.length();
		vector < vector < string > > record;
		vector < string > track;
		this->palindromicPart(record, track, 0, n, text);
		// Display calculated palindromic substring
		for (int i = 0; i < record.size(); ++i)
		{
			for (int j = 0; j < record.at(i).size(); ++j)
			{
				cout << "  " << record.at(i).at(j);
			}
			cout << "\n";
		}
	}
};
int main()
{
	Partition *task = new Partition();
	string text = "minimum";
	// All palindromic substring
	task->palindromicSplit(text);
	return 0;
}

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program
    Print all palindromic partitions of a string
*/
public class Partition
{
	// Check that given substring is palindrome or not
	public Boolean isPalindrome(String text, int first, int last)
	{
		while (first < last)
		{
			if (text[first] != text[last])
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first++;
			last--;
		}
		return true;
	}
	// Find all palindromic substring in given text
	public void palindromicPart(List < List < string >> record, 
                                 List < string > track, int start, 
                                 int n, String text)
	{
		if (start >= n)
		{
			record.Add(new List < string > (track));
		}
		else
		{
			for (int i = start; i < n; i++)
			{
				if (this.isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track.Add(text.Substring(start, i + 1 - start));
					this.palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.RemoveAt(track.Count - 1);
				}
			}
		}
	}
	public void palindromicSplit(String text)
	{
		int n = text.Length;
		List < List < string >> record = new List < List < string >> ();
		List < string > track = new List < string > ();
		this.palindromicPart(record, track, 0, n, text);
		// Display calculated palindromic substring
		for (int i = 0; i < record.Count; ++i)
		{
			for (int j = 0; j < record[i].Count; ++j)
			{
				Console.Write("  " + record[i][j]);
			}
			Console.Write("\n");
		}
	}
	public static void Main(String[] args)
	{
		Partition task = new Partition();
		String text = "minimum";
		// All palindromic substring
		task.palindromicSplit(text);
	}
}

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
package main
import "fmt"
/*
    Go program
    Print all palindromic partitions of a string
*/

// Check that given substring is palindrome or not
func isPalindrome(text string, first int, last int) bool {
	for (first < last) {
		if text[first] != text[last] {
			// When boundary characters are different
			return false
		}
		// Change element position
		first++
		last--
	}
	return true
}
// Find all palindromic substring in given text
func palindromicPart(track[]string, start int, n int, text string) {
	if start >= n {
	    fmt.Println(track)
	 
	} else {
		runes := []rune(text)
		for i := start ; i < n ; i++ {
			if isPalindrome(text, start, i) == true {
				// Add palindromic substring
				track = append(track, string(runes[start:  i + 1 ]))
				palindromicPart(track, i + 1, n, text)
				// Remove added current substring
				track = track[:len(track)-1]
			}
		}
	}
}
func palindromicSplit(text string) {
	var n int = len(text)
	var track []string
	// Display calculated palindromic substring
	palindromicPart(track, 0, n, text)

}
func main() {
	
	var text string = "minimum"
	// All palindromic substring
	palindromicSplit(text)
}

input

[m i n i m u m]
[m i n i mum]
[m ini m u m]
[m ini mum]
[minim u m]
<?php
/*
    Php program
    Print all palindromic partitions of a string
*/
class Partition
{
	// Check that given substring is palindrome or not
	public	function isPalindrome($text, $first, $last)
	{
		while ($first < $last)
		{
			if ($text[$first] != $text[$last])
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			$first++;
			$last--;
		}
		return true;
	}
	// Find all palindromic substring in given text
	public	function palindromicPart(&$record, $track, 
                                      $start, $n, $text)
	{
		if ($start >= $n)
		{
			$record[] = $track;
		}
		else
		{
			for ($i = $start; $i < $n; $i++)
			{
				if ($this->isPalindrome($text, $start, $i) == true)
				{
					// Add palindromic substring
					$track[] = substr($text, $start, $i + 1 - $start) ;
					$this->palindromicPart($record, $track, $i + 1, $n, $text);
					// Remove added current substring
					array_pop($track);
				}
			}
		}
	}
	public	function palindromicSplit($text)
	{
		$n = strlen($text);
		$record = array();
		$track = array();
		$this->palindromicPart($record, $track, 0, $n, $text);
		// Display calculated palindromic substring
		for ($i = 0; $i < count($record); ++$i)
		{
			for ($j = 0; $j < count($record[$i]); ++$j)
			{
				echo("  ".$record[$i][$j]);
			}
			echo("\n");
		}
	}
}

function main()
{
	$task = new Partition();
	$text = "minimum";
	// All palindromic substring
	$task->palindromicSplit($text);
}
main();

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
/*
    Node JS program
    Print all palindromic partitions of a string
*/
class Partition
{
	// Check that given substring is palindrome or not
	isPalindrome(text, first, last)
	{
		while (first < last)
		{
			if (text.charAt(first) != text.charAt(last))
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first++;
			last--;
		}
		return true;
	}
	// Find all palindromic substring in given text
	palindromicPart(record, track, start, n, text)
	{
		if (start >= n)
		{
			record.push([...track]);
		}
		else
		{
			for (var i = start; i < n; i++)
			{
				if (this.isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track.push(text.substring(start, i + 1 ));
					this.palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.pop();
				}
			}
		}
	}
	palindromicSplit(text)
	{
		var n = text.length;
		var record = [];
		var track = [];
		this.palindromicPart(record, track, 0, n, text);
		// Display calculated palindromic substring
		for (var i = 0; i < record.length; ++i)
		{
			for (var j = 0; j < record[i].length; ++j)
			{
				process.stdout.write("  " + record[i][j]);
			}
			process.stdout.write("\n");
		}
	}
}

function main()
{
	var task = new Partition();
	var text = "minimum";
	// All palindromic substring
	task.palindromicSplit(text);
}
main();

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
#    Python 3 program
#    Print all palindromic partitions of a string
class Partition :
	#  Check that given substring is palindrome or not
	def isPalindrome(self, text, first, last) :
		while (first < last) :
			if (text[first] != text[last]) :
				#  When boundary characters are different
				return False
			
			#  Change element position
			first += 1
			last -= 1
		
		return True
	
	#  Find all palindromic substring in given text
	def palindromicPart(self, record, track, start, n, text) :
		if (start >= n) :
			record.append(track.copy())
		else :
			i = start
			while (i < n) :
				if (self.isPalindrome(text, start, i) == True) :
					#  Add palindromic substring
					track.append(text[start: i + 1])
					self.palindromicPart(record, track, i + 1, n, text)
					#  Remove added current substring
					del track[len(track) - 1]
				
				i += 1
			
		
	
	def palindromicSplit(self, text) :
		n = len(text)
		record = []
		track = []
		self.palindromicPart(record, track, 0, n, text)
		i = 0
		#  Display calculated palindromic substring
		while (i < len(record)) :
			j = 0
			while (j < len(record[i])) :
				print("  ", record[i][j], end = "")
				j += 1
			
			print(end = "\n")
			i += 1
		
	

def main() :
	task = Partition()
	text = "minimum"
	#  All palindromic substring
	task.palindromicSplit(text)

if __name__ == "__main__": main()

input

   m   i   n   i   m   u   m
   m   i   n   i   mum
   m   ini   m   u   m
   m   ini   mum
   minim   u   m
#    Ruby program
#    Print all palindromic partitions of a string
class Partition 
	#  Check that given substring is palindrome or not
	def isPalindrome(text, first, last) 
		while (first < last) 
			if (text[first] != text[last]) 
				#  When boundary characters are different
				return false
			end
			#  Change element position
			first += 1
			last -= 1
		end

		return true
	end

	#  Find all palindromic substring in given text
	def palindromicPart(record, track, start, n, text) 
		if (start >= n) 
			record.push(track.map(&:clone))
		else
 
			i = start
			while (i < n) 
				if (self.isPalindrome(text, start, i) == true) 
					#  Add palindromic substring
					track.push(text[start...i + 1])
					self.palindromicPart(record, track, i + 1, n, text)
					#  Remove added current substring
					track.delete_at(track.length - 1)
				end

				i += 1
			end

		end

	end

	def palindromicSplit(text) 
		n = text.length
		record = []
		track = []
		self.palindromicPart(record, track, 0, n, text)
		i = 0
		#  Display calculated palindromic substring
		while (i < record.length) 
			j = 0
			while (j < record[i].length) 
				print("  ", record[i][j])
				j += 1
			end

			print("\n")
			i += 1
		end

	end

end

def main() 
	task = Partition.new()
	text = "minimum"
	#  All palindromic substring
	task.palindromicSplit(text)
end

main()

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m

import scala.collection.mutable._;
/*
    Scala program
    Print all palindromic partitions of a string
*/
class Partition()
{
	// Check that given substring is palindrome or not
	def isPalindrome(text: String, start: Int, end: Int): Boolean = {
      	var first = start;
      	var last  = end;
		while (first < last)
		{
			if (text.charAt(first) != text.charAt(last))
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first += 1;
			last -= 1;
		}
		return true;
	}
	// Find all palindromic substring in given text
	def palindromicPart(record: ArrayBuffer[ArrayBuffer[String]], 
      					track: ArrayBuffer[String], start: Int, 
       					 n: Int, text: String): Unit = {
		if (start >= n)
		{
			record.append(track.clone);
		}
		else
		{
			var i: Int = start;
			while (i < n)
			{
				if (isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track += text.substring(start, i + 1);
					palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.remove(track.size - 1);
				}
				i += 1;
			}
		}
	}
	def palindromicSplit(text: String): Unit = {
		var n: Int = text.length();
		var record: ArrayBuffer[ArrayBuffer[String]] = 
          new ArrayBuffer[ArrayBuffer[String]]();
		var track: ArrayBuffer[String] = 
          new ArrayBuffer[String]();
		palindromicPart(record, track, 0, n, text);
		var i: Int = 0;
		// Display calculated palindromic substring
		while (i < record.size)
		{
			var j: Int = 0;
			while (j < record(i).size)
			{
				print("  " + record(i)(j));
				j += 1;
			}
			print("\n");
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Partition = new Partition();
		var text: String = "minimum";
		// All palindromic substring
		task.palindromicSplit(text);
	}
}

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
import Foundation;
/*
    Swift 4 program
    Print all palindromic partitions of a string
*/
class Partition
{
	// Check that given substring is palindrome or not
	func isPalindrome(_ data: String, _ front: Int, _ tail: Int) -> Bool
	{
        var first = front ;
      	var last = tail;
      	let text = Array(data);
		while (first < last)
		{
			if (text[first]  != text[last])
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first += 1;
			last -= 1;
		}
		return true;
	}
	// Find all palindromic substring in given text
	func palindromicPart(_ record: inout[[String]], 
      					 _ track: inout[String], _ start: Int, 
                         _ n: Int, _ text: String)
	{
		if (start >= n)
		{
			record.append(track);
		}
		else
		{
			var i: Int = start;
			while (i < n)
			{
				if (self.isPalindrome(text, start, i) == true)
				{
                  	let s = text.index(text.startIndex, offsetBy: start)
					let e = text.index(text.endIndex, 
                                         offsetBy: -(n-(1+i)))
					// Add palindromic substring
					track.append(String(text[s..<e]));
					self.palindromicPart(&record, &track, i + 1, n, text);
					// Remove added current substring
					track.removeLast();
				}
				i += 1;
			}
		}
	}
	func palindromicSplit(_ text: String)
	{
		let n: Int = text.count;
		var record: [[String]] = [[String]]();
		var track: [String] = [String]();
		self.palindromicPart(&record, &track, 0, n, text);
		var i: Int = 0;
		// Display calculated palindromic substring
		while (i < record.count)
		{
			var j: Int = 0;
			while (j < record[i].count)
			{
				print("  ", record[i][j], terminator: "");
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
		}
	}
}
func main()
{
	let task: Partition = Partition();
	let text: String = "minimum";
	// All palindromic substring
	task.palindromicSplit(text);
}
main();

input

   m   i   n   i   m   u   m
   m   i   n   i   mum
   m   ini   m   u   m
   m   ini   mum
   minim   u   m
/*
    Kotlin program
    Print all palindromic partitions of a string
*/
class Partition
{
	// Check that given substring is palindrome or not
	fun isPalindrome(text: String, start: Int, end: Int): Boolean
	{
      	var first = start;
      	var last = end;
		while (first < last)
		{
			if (text.get(first) != text.get(last))
			{
				// When boundary characters are different
				return false;
			}
			// Change element position
			first += 1;
			last -= 1;
		}
		return true;
	}
	// Find all palindromic substring in given text
	fun palindromicPart(record: MutableList < MutableList < String >>  , 
                        track : MutableList < String >  ,
                        start : Int, n: Int, text: String): Unit
	{
		if (start >= n)
		{
			record.add(track.toMutableList());
		}
		else
		{
			var i: Int = start;
			while (i < n)
			{
				if (this.isPalindrome(text, start, i) == true)
				{
					// Add palindromic substring
					track.add(text.substring(start, i + 1));
					this.palindromicPart(record, track, i + 1, n, text);
					// Remove added current substring
					track.removeAt(track.size - 1);
				}
				i += 1;
			}
		}
	}
	fun palindromicSplit(text: String): Unit
	{
		val n: Int = text.length;
		var record: MutableList < MutableList < String >> = 
          mutableListOf < MutableList < String >> ();
		var track = 
          mutableListOf < String > ();
		this.palindromicPart(record, track, 0, n, text);
		var i: Int = 0;
		// Display calculated palindromic substring
		while (i < record.size)
		{
			var j: Int = 0;
			while (j < record[i].size)
			{
				print("  " + record[i][j]);
				j += 1;
			}
			print("\n");
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Partition = Partition();
	val text: String = "minimum";
	// All palindromic substring
	task.palindromicSplit(text);
}

input

  m  i  n  i  m  u  m
  m  i  n  i  mum
  m  ini  m  u  m
  m  ini  mum
  minim  u  m
Last updated on by Kalkicode




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