Print all Palindromic Partitions

Given a string, print all palindromic partitions of the given string.
Palindromic partitioning of a string is dividing the string into parts such that each part is a palindrome.

If abcb is a string, then
a-b-c-b and a-bcb will be palindormic partitions of the string.

a-b-cb, ab-cb, ab-c-b etc are partitions but not palindromic partitions of the string abcb.
b-c-b is palindromic but not a partition of the string abcb.

Example:

Input:
IDeserve
Output:
I-D-e-s-e-r-v-e
I-D-ese-r-v-e

Input:
banana
Output:
b-a-n-a-n-a
b-a-n-ana
b-a-nan-a
b-ana-n-a
b-anana


Question Asked in

Amazon


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

The solution is recursive where we find the palindromic substring of the string, add it to the output and recursively traverse for the remaining part of the string to find other possible palindromic substrings and hence partitions.

Steps:
1. If begin == end, print the current output string.
2. Loop for i = begin to end,
    if substring of input string from begin to i is a palindrome then add substring from begin to i to the output string and recursively call for rest of the substring from i+1 to end.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a string, print all palindromic partitions of the given string.
 *
 * @author Saurabh
 */
public class AllPalindromicPartitions {
	public static boolean ispalin(String input, int begin, int end) {
		while (begin < end) {
			if (input.charAt(begin) != input.charAt(end))
				return false;
			begin++;
			end--;
		}
		return true;
	}

	public static void printpart(String input, String output, int begin, int end) {
		if (begin == end) {
			System.out.println(output);
			return;
		}
		int n = input.length();
		String delimiter = "-";
		for (int i = begin; i < end; i++) {
			if (ispalin(input, begin, i)) {
				if (i+1 == n) {
					delimiter = "";
				}
				printpart(input, output + input.substring(begin, i+1) + delimiter, i + 1, end);
			}
		}
	}

	public static void main(String[] args) {
		String input = "abcb";
		String output = "";
		int begin = 0;
		int end = input.length();
		printpart(input, output, begin, end);
	}
}
		

Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer