"Any fool can write code that a computer can understand. Good programmers write code that humans can understand."
- Martin Fowler
Minimum Palindromic Cuts
Welcome back, dear reader. So, how is it going? In this article, we
will discuss a very interesting and challenging problem called MINIMUM
PALINDROMIC CUTS. So, what does this question say?
We are given a string as the input and we have to tell the
minimum number of cuts that partition every part of the string into a
palindrome. For instance, consider the example given below:
As you can see in the image above, we have minimum 2 cuts which make every part of the string a palindrome. We recommend you refer to the MINIMUM PALINDROMIC CUTS VIDEO (0:00-1:04) to understand the problem completely and clear your doubts regarding it. We suggest you try to solve this problem on your own first and then refer to the solution for building your concepts strong.
Left-Right Strategy:
Complexity: Time Complexity:
O(n3) where n is the length of the input string
Complexity: Space Complexity:O(n2)
Approach
Explanation:
Dear reader, we recommend you refer to the ROD CUTTING VIDEO to understand both the strategies that we have discussed there as they are the basis for discussion in this article
Let us start with the left-right strategy. We have the input string "abccbc". In this input string, let us start applying the cuts from the left to the right as shown in the figure.
Now let us assume we know how to calculate the minimum palindromic cuts in each partitioned string.
For instance, in the first string, the minimum palindromic cuts required for the left half is 0 as "a" is already a palindrome. In the remaining part of the string, the minimum palindromic cut is 1 i.e. splitting it up into "bccb" and "c". So, the total number of minimum palindromic cuts will be 0 (for the left half) + 1(for the right half) + 1 (for this partition which has divided it into left and right half) = 2.
This can be calculated for every string:
So, we can see that there are 2 cases where we require only 2 partitions. The answer can be any one of them but we don't care about that. We just want the minimum palindromic cuts and that answer is 2. So, let us try to implement this procedure.
Filling the Boolean Matrix
Let us consider the following dp1 matrix of Boolean type.
So, we have constructed this matrix following the gap strategy and you already know that the cells that are marked with a cross are invalid as the starting point for those cells is larger than the end point.
This is a Boolean type of matrix. So, what does each cell in this matrix represent?
As you can see from the image above, dp1[1][3] represents whether the string "bcc" is a palindrome or not. Similarly, we have all the rest cells as shown in the image below
Now let us start filling this matrix. Let us start with the main diagonal. As you can see, the main diagonal represents all the individual characters of the string. So, these will be palindromes, right? So, we will fill true in all of them.
Now, let us come to the right of this main diagonal i.e. let us talk upon the diagonal where the gap between the row number and the column number is 1.
This diagonal has all the strings of length 2. So, a string of length 2 can only be a palindrome if both the characters of the string are the same. So, for such strings, we will put true in the matrix and we will put false otherwise.
Now, let us start filling the diagonal where the difference between the row value and column value is 2. From here, things start getting interesting. A string can only be a palindrome if its initial character and last character are the same and the string remaining in the middle is a palindrome itself.
So, we will fill this diagonal and the further diagonals using this concept only. So, the result will be as shown:
Now that we have completely filled the Boolean matrix, let us create a matrix of integers and try to fill that matrix with the minimum number of palindromic cuts.
As we know that the main diagonal will have all the strings of length 1. So, they all are already palindromes and do not need any cuts. So, we will put all values 0 in the main diagonal.
In the next diagonal, where the gap between the row values and the column values is 2, we have all the strings of length 2. We will check from the Boolean matrix above that which of them is a palindrome and which of them is not. If the string that we are currently on in the integer dop matrix is a palindrome, we do not need to cut it and the dp2[i][j]=0 else, we have to apply one cut to make it a palindrome. Why? Think!!!!
Now, we are in the next diagonal. Here, let us look at dp2[0][2]. This string can be cut in 2 ways as shown below:
So, if we cut such that we have 2 substrings "a" and "bc", the string "a" is a palindrome and does not require any cuts. The string "bc" on the other hand, is not a palindrome and it requires a minimum 1 cut to make partition palindromes. So, minimum 2 cuts will be required for this string such that every partition is a palindrome if we make the first cut after "a". Otherwise, if we make the first cut after "b" such that the substrings are now "ab" and "c", we will again get 2 cuts as the answer.
So, the minimum out of them is 2. So, we will store 2 at dp2[0][2].
Let us now see this for the next string i.e. dp2[1][3] or "bcc". The string can be cut I the following ways:
So, we can clearly see that the first cut after "b" will give us less number of cuts. Where can we see this in the matrix? Have a look at the diagram given below:
As you can see, we can count the minimum number of cuts if the first cut is made after "b" by dp2[1][1] + dp2[2][3] +1=0+0+1=1. (shown by orange in the matrix)
Similarly, we can find the minimum number of cuts if the first cut is made after "c" resulting in "bc" as one substring and "c" as the other by dp2[1][2] + dp2[3][3] +1= 1+0+1=2. So, the minimum out of them is 1 and will be stored in the matrix.
So, this is how we are filling this matrix. We recommend you try to fill this matrix on your own completely. The completely filled matrix is shown below:
Dear reader, we recommend you refer to the solution video to understand the procedure explained till here. We will now write the code for this procedure:
The above code is explained in the solution video. We recommend you refer to it to understand the code in depth. Let us analyze its complexity and make it better.
Analysis
Time Complexity:
The time complexity of this solution is O(n3) as we have 3 for loops nested into one another (see the above code).
Space Complexity:
The space complexity of this code is O(n2) as we have used two 2-D arrays (one Boolean and other of type integer) to solve this problem.
Palindromic Prefix/Suffix Cut Method:
We will use the Boolean array here too. But, this time we will not make a cut after every character; rather, we will make a cut only if we find a palindromic prefix. (see the image below)
We can also cut the palindromic suffix instead of prefix as shown in the image below:
First we had the string "abccbc" and we started cutting only the palindromic suffixes. The image is self-explanatory that the minimum number of cuts are 2 and that will be our answer.
What will we do?
We will use a single dimensional array now instead of a 2-D matrix as shown below:
So, if this array is named dp2 the, dp[0]=0 and dp[1]=1. Why? Think about this!!!
This is because string "a" is a palindrome so 0 cuts and string "ab" is not a palindrome so, we will apply one cut to make the partitions a palindrome.
Let us have a look at dp[2] i.e. string "abc". If we break this by palindromic suffix cut method, we have:
So, dp[2]=2. If we move to string "abcc", we have:
Similarly, we can fill the entire matrix.
So, you will either find those substrings that are already filled in this array or those which are palindromes for which the score will be 0.
We recommend you refer to the solution video to understand the complete procedure and also the code below
Code
import java.io.*;
import java.util.*;
public class Main {
public static int minPalindromicCut(String s) {
int n = s.length();
boolean[][] dp = new boolean[s.length()][s.length()];
for (int gap = 0; gap < s.length(); gap++) {
int si = 0, ei = gap;
while (ei < s.length()) {
if (gap == 0) {
dp[si][ei] = true;
} else if (gap == 1) {
dp[si][ei] = s.charAt(si) == s.charAt(ei);
} else {
if (s.charAt(si) == s.charAt(ei)) {
dp[si][ei] = dp[si + 1][ei - 1];
} else {
dp[si][ei] = false;
}
}
si++;
ei++;
}
}
int[] cuts = new int[n];
for (int i = 0; i < n; i++) {
if (dp[0][i] == true) {
cuts[i] = 0;
} else {
cuts[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if(dp[j + 1][i] == true && 1 + cuts[j] < cuts[i]){
cuts[i] = 1 + cuts[j];
}
}
}
}
return cuts[n - 1];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.nextLine();
System.out.println(minPalindromicCut(str));
}
}
java;
true";
We hope that you have understood the complete procedure. You may refer to the complete solution video to clear all your doubts and understand this solution in depth.
Analysis
Time Complexity:
The time complexity of the above solution is O(n2) due to the nested for loop
Space Complexity:
The space complexity of the above solution is O(n2) as we have used a 2-D matrix of size n x n and a one-dimensional array of size n.
So, dear reader, we hope that you have understood the complete solution. We request you to refer to the complete solution video once as it will clear all your doubts and make your concepts strong. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you don't want to miss:
We suggest that you should refer to the ROD-CUTTING PROBLEM before this problem as it will become easy for you to understand things faster and in more-depth here.
We also suggest that you code both the methods once yourself and try to submit the solution on the portal with both the approaches that you have learnt once without taking any help. This will help you retain the concept for a long time. So, keep practicing and working hard. Till then, Happy Coding!!!
