Palindrome Partitioning problem in Java

In this article, you will be acknowledged about partitioning of the palindrome. It can be done in many ways. This article makes sure every method is discussed.

Palindrome

If a string remains unchanged whether it is read from the left to the right or the right to the left, it is considered to be a palindrome.

Palindrome Partitioning

When a string is partitioned into palindromes, it is done so that each substring created from the original string is really a palindrome in and of itself. In the Java palindrome partitioning issue, we provide the lowest number of cuts needed to convert each of the provided string's substrings into a palindrome. Let's break it down with the aid of some examples.

A matrix chain multiplication issue variant is this one. The string is simply returned as 0, if it is a palindrome. If not, we attempt to make cuts in every location that is feasible, recursively determine the cost for each cut, and then return the minimal value, similar to a Matrix Chain Multiplication issue.

Take str as the input string, and let minPalPartion() return the function that requires the fewest cuts to partition a palindrome.

Example:

Str = “madam”

At most cuts needed to the above string are 0. Since the string is a palindrome.

Str = “kebab”

At most cuts needed to the above string are 2. Since the string is not a palindrome. We may divide the provided text into 3 substrings using the 2 cuts, each of which is a palindrome.

There are many approaches in which a palindrome partitioning can be achieved. They are

By recursion
By Dynamic programming
By memorization

By Recursion

Let us understand the partitioning of palindrome by recursion method

File name: Recurpalin.java

// Java program for implementation of palindrome partitioning by recursion method
public class Recurpalin
{
static boolean isPalindrome(String string, int i, int j)
{
while(i < j)
{
if(string.charAt(i) != string.charAt(j))
return false;
i++;
j--;
}
return true;
}
static int minPalPartion(String string, int i, int j)
{
if( i >= j || isPalindrome(string, i, j) )
return 0;
int ans = Integer.MAX_VALUE, count;
for(int k = i; k < j; k++)
{
count = minPalPartion(string, i, k) +
minPalPartion(string, k + 1, j) + 1;
ans = Math.min(ans, count);
}
return ans;
}
public static void main(String args[])
{
String str = "kebab";
System.out.println("At most cuts needed in "
+ "Palindrome Partitioning is " + minPalPartion(str, 0, str.length() - 1));
}
}

Output

At most cuts needed in Palindrome Partitioning is 2

By Dynamic Programming

The dynamic programming solution is shown below. It seems to use the calculated values and stores the responses to the subproblems in two arrays. Let u sunderstand it through the program flow.

Let us understand the program flow for achieving the palindrome partitioning. The approach that discussed below implements the dynamic programming. It is not really a program but the function body of how the methodology is implemented for partitioning the palindrome. It was proved that this approach isn’t the perfect approach. We are using for loops that are nested to a threshold of three to locate the solution. This consumes a lot of time for execution of program. So an optimized approach is also discovered.

class Dynampalin {


public static int minCut(String a)
{
int[] cut = new int[a.length()];
boolean[][] palindrome = new boolean[a.length()][a.length()];


for (int i = 0; i < a.length(); i++) {
int minCut = i;
for (int j = 0; j <= i; j++) {
if (a.charAt(i) == a.charAt(j) && (i - j < 2 || palindrome[j + 1][i - 1])) {
palindrome[j][i] = true;
minCut = Math.min(minCut, j == 0 ? 0 : (cut[j - 1] + 1));
}
}
cut[i] = minCut;
}


return cut[a.length() - 1];
}
}

Now let us go through the program that runs with a optimized approach. The interviewer will typically reject the above solution, but they can also ask that you enhance it. The offered solution never possesses the third level of for-loop nesting. The logic after optimization has been found that the time consumption or the time complexity is comparatively less than the previously discussed function. Hence this method is more often used for the purpose of palindrome partitioning.

File name: Dynampalin1.java

//Java program for implementation of palindrome partitioning by dynamic programming    //method
public class Dynampalin1{
static int minPalPartion(String str)
{
int n = str.length();
int[] C = new int[n];
boolean[][] P = new boolean[n][n];


int i, j, k, L; 
for (i = 0; i < n; i++) {
P[i][i] = true;
}
/* Substring length L is. Consider all substrings with lengths ranging from 2 to n as you build the solution from the bottom up.*/
for (L = 2; L <= n; L++) {
// Different starting indexes should be established for a substring of\
                                       //length L.
for (i = 0; i < n - L + 1; i++) {
j = i + L - 1; // Set ending index
// We just need to compare two characters if L is 2. 
                                                      //Otherwise,two corner characters must be checked.
if (L == 2)
P[i][j] = (str.charAt(i) == str.charAt(j));
else
P[i][j] = (str.charAt(i) == str.charAt(j)) && P[i + 1][j - 1];
}
}
for (i = 0; i < n; i++) {
if (P[0][i] == true)
C[i] = 0;
else {
C[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (P[j + 1][i] == true && 1 + C[j] < C[i])
C[i] = 1 + C[j];
}
}
}
// Obtain the string's minimum cut value.
return C[n - 1];
}
public static void main(String args[])
{
String str = "kebab";
System.out.println("At most cuts needed in "
+ "Palindrome Partitioning"
+ " is " + minPalPartion(str));
}
}

Output

At most cuts needed in Palindrome Partitioning is 2

By Memorization

The fundamental concept is to cache the sporadic results computed by recursive functions. These outcomes can be placed in a hashmap or unordered map.

The starting and ending indexes of the text will be used to construct the keys for such hashmap, so ["start index".append("end index")] would be the key.

Let us understand the below program for understanding the above approach.

File name: Memopalin.java

import java.io.*;
import java.util.*;


class Memopalin {
// Leveraging memorization to overcome the partition problems.


// method to determine whether an input string is a palindrome
static boolean ispalindrome(String input, int start, int end)
{
// Using the two-pointer method to verify palindrome
while (start < end) {
if (input.charAt(start) != input.charAt(end))
return false;
start++;
end--;
}
return true;
}


// method to retrieve keys for hashmap
static String convert(int a, int b)
{
return String.valueOf(a) + "" + String.valueOf(b);
}


/* Returns the smallest number of cuts necessary to divide a string into sections where each one is a palindrome.*/
static int minpalparti_memo(String input, int i, int j, HashMap<String, Integer> memo)
{
if (i > j)
return 0;
// The input string's key
String ij = convert(i, j);


/* If the number of partitions for the string "ij" has already been determined, then use the Hashmap to return the calculated result.*/
if (memo.containsKey(ij)) {
return memo.get(ij);
}
// A palindrome exists for every String of size 1.
if (i == j) {
memo.put(ij, 0);
return 0;
}
if (ispalindrome(input, i, j)) {
memo.put(ij, 0);
return 0;
}
int minimum = Integer.MAX_VALUE;
// Make cuts from I to j in every direction that is possible.
for (int k = i; k < j; k++) {
int left_min = Integer.MAX_VALUE;
int right_min = Integer.MAX_VALUE;
String left = convert(i, k);
String right = convert(k + 1, j);


// if the left cut is already clear
if (memo.containsKey(left)) {
left_min = memo.get(left);
}
// if the appropriate cut is already discovered
if (memo.containsKey(right)) {
right_min = memo.get(right);
}


// the left as well as right strings are calculated recursively
if (left_min == Integer.MAX_VALUE)
left_min = minpalparti_memo(input, i, k, memo);
if (right_min == Integer.MAX_VALUE)
right_min = minpalparti_memo(input, k + 1, j, memo);


// minimising all potential cuts to k
minimum = Math.min(minimum, left_min + 1 + right_min);
}
memo.put(ij, minimum);
// For the entire string, return the minimum cut value.
return memo.get(ij);
}

public static void main(String args[])
{
String input = "kebab";
HashMap<String, Integer> memo = new HashMap<>();
System.out.println(minpalparti_memo(input, 0, input.length() - 1, memo));
}
}

Output

At most cuts required in palindrome partitioning are 2

← Prev Next →

Palindrome Partitioning problem in Java

Palindrome