Problem Statement
Partitioning of any string ss is considered to be palindrome partitioning if every substring of the partition is a palindrome.
In this problem, you have been given a string ss and you need to determine the fewest cuts needed for a palindrome partitioning of the given string.
Examples
Example 1
Input : abaaab
Output :
1
Explanation : abaaab can be partitioned into a|baaab. It can be shown that no other palindrome partition is possible with less than 1 cut.
Example 2
Input abccba
Output
0
Explanation Since the string abccba is already a palindrome, hence no need to make any cut.
Example 3
Input : abcda
Output :
4
Explanation : The only possible way is to make cut at every possible position i.e.i.e. a|b|c|d|a.
Constraints
- 1≤∣s∣≤10001≤∣s∣≤1000
- All characters in ss are only lowercase English characters.
Approach 1: Using Recursion
Before beginning with the solution let’s make some observations.
- The maximum possible cuts for a string ss of length n is n−1.
- The minimum possible cuts that we can make is 0 (when s is the palindrome itself).
As part of our brute force approach, we will use the concept of recursion. In the recursive function (say minimumCut) we will have some base-cases based on the observations we made, and in the main logic, we will try to make a cut at every possible place and then we recur for the left and the right string obtained after cutting.
So the algorithm is as follows –
- Let’s say we have a string ss of length nn, we will define an integer type recursive function minimumCut that will take three arguments Viz. the string itself, low index, and high index. The value of low and high will be 0 and n-1 initially.
- Now inside the function, we will check if string s[low…high] is a palindrome or not, if the condition holds we need not make any cut, hence we will return 0.
- Otherwise, we define a variable (say ans) and initialize its value with a very large number.
- Iterate from k=low to k=high−1 and do the following –
- Lets say we make a cut at index k, which splits string s[low…high] to left string (s[low…k]) and right string (s[(k+1)…high]). This cut counts for making exactly one cut.
- Count cuts needed in the left string obtained by recurring for the left string and store them in a variable (say left).
- Count cuts needed in the left string obtained by recurring for the right string and store them in a variable (say right).
- If the inequality 1 + left + right < ans holds, then update the value of ans.
- Return the value of ans.
Also, we will have a helper function to check if the string s[low…high] is a palindrome or not (say isPalindrome) that will take three arguments Viz. the string itself, low index, and high index. The logic of the same is as follows –
- Use a while loop to iterate over the string, until the inequality low<high holds.
- In each iteration, if s[low] != s[high] holds true, return false which means s[low…high] is not a palindrome.
- Otherwise, increase low by 1 and decrease high by 1.
- Return true at last.
Pseudocode
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
function minimumCut (s, low, high){
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
If (low >= high OR isPalindrome (s, low, high))
return 0
// Initialize ans with a very large value.
int ans = Infinity
For (k = low To k = high - 1){
// Cuts needed in the left part.
left = minimumCut (s, low, k)
// Cuts needed in the right part
int right = minimumCut (s, k+1, high)
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right
// Update the ans.
If (total < ans)
ans = total;
// Return ans;
return ans;
function end
Java Implementation
public class Main{
// Function to check if the string s[low...high]
// is palindrome or not.
static boolean isPalindrome (char s[], int low, int high){
// Iterate while low < high
while (low<high){
// If the character at low and high
// do not matches return false.
if (s[low++] != s[high--])
return false;
}
return true;
}
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
static int minimumCut (char s[], int low, int high){
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
if(low >= high || isPalindrome (s, low, high))
return 0;
// Initialize ans with a very large value.
int ans = Integer.MAX_VALUE;
for (int k = low; k < high; k++){
// Cuts needed in the left part.
int left = minimumCut (s, low, k);
// Cuts needed in the right part.
int right = minimumCut (s, k+1, high);
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right;
// Update the ans.
if (total < ans)
ans = total;
}
// Return ans
return ans;
}
// Main function
public static void main (String args[]){
String s = "abaaab";
int count = minimumCut(s.toCharArray(), 0, s.length() - 1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abccba";
count = minimumCut(s.toCharArray(), 0, s.length() - 1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abcda";
count = minimumCut(s.toCharArray(), 0, s.length() - 1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
}
}
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
// Function to check if the string s[low...high]
// is palindrome or not.
bool isPalindrome (string s, int low, int high){
// Iterate while low < high
while (low<high){
// If the character at low and high
// do not matches return false.
if (s[low++] != s[high--])
return false;
}
return true;
}
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
int minimumCut (string s, int low, int high){
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
if(low >= high || isPalindrome (s, low, high))
return 0;
// Initialize ans with a very large value.
int ans = INT_MAX;
for (int k = low; k < high; k++){
// Cuts needed in the left part.
int left = minimumCut (s, low, k);
// Cuts needed in the right part.
int right = minimumCut (s, k+1, high);
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right;
// Update the ans.
if (total < ans)
ans = total;
}
// Return ans
return ans;
}
// Main function
int main(){
string s = "abaaab";
int count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abccba";
count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abcda";
count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
}
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Python Implementation
# Function to check if the string s[low...high]
# is palindrome or not.
def isPalindrome (s, low, high):
# Iterate while low < high
while (low<high):
# If the character at low and high
# do not matches return false.
if (s[low] != s[high]):
return False
low += 1
high-= 1
return True
# Function to find minimum cut for
# palindrome partitoning of s.
# Initially low = 0, high = |s| - 1
def minimumCut (s, low, high):
# If the string s[low...high] is palindrome
# or length of string is <=1 the no cut is needed.
if(low >= high or isPalindrome (s, low, high)):
return 0
# Initialize ans with a very large value.
ans = 999999999
for k in range (low, high):
# Cuts needed in the left part.
left = minimumCut (s, low, k)
# Cuts needed in the right part.
right = minimumCut (s, k+1, high)
# Total cuts needed (including) cuts
# at current position
total = 1 + left + right
# Update the ans.
if (total < ans):
ans = total
# Return ans
return ans
# Driver code
s = "abaaab"
count = minimumCut(s, 0, len(s)-1)
print ("Minmum cuts to partiton",
s, "is", count)
s = "abccba"
count = minimumCut(s, 0, len(s)-1)
print ("Minmum cuts to partiton",
s, "is", count)
s = "abcda"
count = minimumCut(s, 0, len(s)-1)
print ("Minmum cuts to partiton",
s, "is", count)
Output –
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Complexity Analysis
- Time Complexity – There are 2n possibilities of partitioning the string of length n, and for each possibility, we are checking if the string is a palindrome that costs O(n) time. Hence the overall time complexity is O(n×2n).
- Space Complexity – We are not using any auxiliary data structure to store the results, hence O(1) extra space is required. But, as it is a recursive function and the height of the recursive tree is O(n) hence overall space complexity is O(n).
Approach 2: Memoization
In the previous section, we have seen the recursive approach, and it is easily observable that there are many subproblems (substrings) for which we are calculating our answer again and again. This suggests using Dynamic Programming, so we will be using the Top-down DP by creating a memo table (say dp). The approach of DP with memoization is almost the same as the simple recursive approach with the only change that here we will check if the answer of s[low…high] has already been calculated then we will simply return it otherwise we will solve for s[low…high] .
The algorithm is as follows
- Let’s say we have a string ss of length nn, we will define an integer type recursive function minimumCut that will take three arguments Viz. the string itself, low index, and high index. The value of low and high will be 0 and n-1 initially.
- Inside the function firstly check if the answer has already been calculated. If yes then return the same, otherwise proceed to the next steps.
- Then, we will check if string s[low…high] is a palindrome, if the condition holds we need not make any cut, hence we will return 0.
- Otherwise, we define a variable (say ans) and initialize its value with a very large number.
- Iterate from k=low to k=high−1 i.e.i.e. from starting to second last character and do the following –
- Lets say we make a cut between index k and k+1, which splits string s[low…high] to left string (s[low…k]) and right string (s[(k+1)…high]). This cut counts for making exactly one cut.
- Count cuts needed in the left string obtained by recurring for the left string and store them in a variable (say left).
- Count cuts needed in the left string obtained by recurring for the right string and store them in a variable (say right).
- If the inequality 1 + left + right < ans holds, then update the value of ans.
- Store the ans in the memo table and return it.
Pseudocode
dp = 2-D Matrix of size n*n, all entries initialized to -1.
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
function minimumCut (s, low, high){
// Checking if answer for s[low...high] has already
// been calculated.
If (dp[low][high] != -1)
return dp[low][high]
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
If (low >= high OR isPalindrome (s, low, high))
return 0
// Initialize ans with a very large value.
int ans = Infinity
For (k = low To k = high - 1){
// Cuts needed in the left part.
left = minimumCut (s, low, k)
// Cuts needed in the right part
int right = minimumCut (s, k+1, high)
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right
// Update the ans.
If (total < ans)
ans = total;
// Store the ans in dp[low][high].
dp[low][high] = ans
// Return ans;
return ans;
function end
Java Implementation
public class Main{
// DP table
static int dp[][];
static void initializeDPTable (int n){
dp = new int[n][n];
// Initialize all values to be -1.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j] = -1;
}
// Function to check if the string s[low...high]
// is palindrome or not.
static boolean isPalindrome (char[] s, int low, int high){
// Iterate while low < high
while (low<high){
// If the character at low and high
// do not matches return false.
if (s[low++] != s[high--])
return false;
}
return true;
}
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
static int minimumCut (char[] s, int low, int high){
// If answer for s[low...high] has
// already been calculated.
if (dp[low][high] != -1)
return dp[low][high];
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
if(low >= high || isPalindrome (s, low, high))
return 0;
// Initialize ans with a very large value.
int ans = Integer.MAX_VALUE;
for (int k = low; k < high; k++){
// Cuts needed in the left part.
int left = minimumCut (s, low, k);
// Cuts needed in the right part.
int right = minimumCut (s, k+1, high);
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right;
// Update the ans.
if (total < ans)
ans = total;
}
// Store and return ans.
return dp[low][high] = ans;
}
// Main function
public static void main (String args[]){
String s = "abaaab";
initializeDPTable(s.length());
int count = minimumCut(s.toCharArray(), 0, s.length()-1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abccba";
initializeDPTable(s.length());
count = minimumCut(s.toCharArray(), 0, s.length()-1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abcda";
initializeDPTable(s.length());
count = minimumCut(s.toCharArray(), 0, s.length()-1);
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
}
}
Output –
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
int **dp;
void initializeDPTable (int n){
dp = new int*[n];
// Initialize all values to be -1.
for (int i = 0; i < n; i++){
dp[i] = new int[n];
for (int j = 0; j < n; j++)
dp[i][j] = -1;
}
}
// Function to check if the string s[low...high]
// is palindrome or not.
bool isPalindrome (string s, int low, int high){
// Iterate while low < high
while (low<high){
// If the character at low and high
// do not matches return false.
if (s[low++] != s[high--])
return false;
}
return true;
}
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
int minimumCut (string s, int low, int high){
// If the string s[low...high] is palindrome
// or length of string is <=1 the no cut is needed.
if(low >= high || isPalindrome (s, low, high))
return 0;
// Initialize ans with a very large value.
int ans = INT_MAX;
for (int k = low; k < high; k++){
// Cuts needed in the left part.
int left = minimumCut (s, low, k);
// Cuts needed in the right part.
int right = minimumCut (s, k+1, high);
// Total cuts needed (including) cuts
// at current position
int total = 1 + left + right;
// Update the ans.
if (total < ans)
ans = total;
}
// Return ans
return ans;
}
// Main function
int main(){
string s = "abaaab";
initializeDPTable(s.length());
int count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abccba";
initializeDPTable(s.length());
count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abcda";
initializeDPTable(s.length());
count = minimumCut(s, 0, s.length()-1);
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
}
Output –
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Pyhton Implementation
# DP Table
dp = []
# Function to initialize DP Table
def initializeDPTable (n):
dp = [[-1 for i in range(n)] for j in range(n)]
# Function to check if the string s[low...high]
# is palindrome or not.
def isPalindrome (s, low, high):
# Iterate while low < high
while low<high:
# If the character at low and high
# do not matches return false.
if (s[low] != s[high]):
return False
low += 1
high-= 1
return True
# Function to find minimum cut for
# palindrome partitoning of s.
# Initially low = 0, high = |s| - 1
def minimumCut (s, low, high):
# If the string s[low...high] is palindrome
# or length of string is <=1 the no cut is needed.
if(low >= high or isPalindrome (s, low, high)):
return 0
# Initialize ans with a very large value.
ans = 999999
for k in range(low, high):
# Cuts needed in the left part.
left = minimumCut (s, low, k)
# Cuts needed in the right part.
right = minimumCut (s, k+1, high)
# Total cuts needed (including) cuts
# at current position
total = 1 + left + right
# Update the ans.
if (total < ans):
ans = total
# Return ans
return ans
# Driver code
s = "abaaab"
count = minimumCut(s, 0, len(s) - 1)
print ("Minmum cuts to partiton",
s, "is", count)
s = "abccba"
count = minimumCut(s, 0, len(s) - 1)
print ("Minmum cuts to partiton",
s, "is", count)
s = "abcda"
count = minimumCut(s, 0, len(s) - 1)
print ("Minmum cuts to partiton",
s, "is", count)
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Complexity Analysis
- Time Complexity – The time complexity of the above code is O(n3). Because using memoization we have reduced O(2n) to O(n2) (for taking into consideration all possible substrings). But we are still using O(n) for checking if a substring is palindrome or not. Hence overall time complexity is O(n3).
- Space Complexity – Since we are using a 2-D array of dimensions n×n to store the results. Hence the space complexity is O(n2).
Approach 3: Dynamic Programming
In this approach, we will again use Dynamic Programming, but this time we will solve the problem in a bottom-up fashion. The approach is simple, instead of checking whether a string s[low…high] is a palindrome or not.
What we will do is –
- For each pair (low, high) such that 0 <= low <= high < n we will store the if the string s[low…high] is palindrome or not a boolean matrix of size n*n.
- Then, we will define an array (say ans), where ans[i] contains the minimum cut required for the palindrome partitioning of s[0…i].
Let’s say we have a string s of length n. The algorithm for part 1 is as follows –
- Define a boolean 2-D Array (say dp) of dimensions n*n.
- Initialize all its values by false.
- Iterate for gap = 0 to gap = n – 1 and do the following –
- Iterate for i = 0, j = gap to j = n – 1 and do the follwing –
- If gap = 0, we have a string of length 1, which is a palindrome always. Hence we assign dp[i][j] = true.
- If gap = 1, we have a string of length 2, which is palindrome if s[0] = s[1]. Therefore we assign true to dp[i][j] if s[i] = s[j] holds true because it means string s[i…j] is a palindrome.
- Otherwise if gap > 1 (length of the string is greater than 2), we will check if s[i] = s[j], if the condition is true we will make dp[i][j] = dp[i+1][j-1]. This means if s[i] = s[j] then s[i…j] will be palindrome if s[(i+1)…(j-1)] is a palindrome and the result of s[(i+1)…(j-1)] is stored in dp[(i+1)…(j-1)].
- Iterate for i = 0, j = gap to j = n – 1 and do the follwing –
The algorithm of part 2 is as follows –
- Define a array (say ans) of size n, all of its entries are initalize with 0.
- Iterate for i = 1 to i = n – 1 and do the following –
- If dp[0][i] is true, it means s[0…i] is a palindrome, hence no cut is needed.
- Othewise do the following –
- Define a integer (say min) and initialize its value with a very large number.
- Iterate for j = i to j > 0 and do the following –
- If dp[j][i] is true i.e.i.e. s[j…i] is a palindrome and ans[j-1]<min update value of min to ans[j-1].
- Set the value of ans[i] to 1 + min, here 1 denotes the current cut.
- The above step calculates minimum cut required for palindrome partitonin of the current string.
- Print ans[n-1], which is the required answer.
Pseudocode
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
function minimumCut (s, n){
// Table to store palindrome information.
// dp[i][j] = true means, s[i...j] is plaindrome.
dp = boolean array of size n*n
// Iterate from gap = 0 to gap = n-1
For (gap = 0 To gap = n - 1)
// Iterate from i = 0, j = g to j = n-1
For (i = 0, j = g To j = n - 1)
// If gap is 0.
If (gap = 0)
dp[i][j] = true
// Else if gap is 1
Else If (gap == 1)
dp[i][j] = (s[i] == s[j]);
// Otherwise, if gap not equal to 0 or 1
// and s[i] = s[j].
Else If (s[i] == s[j])
// Set dp[i][j] equal to dp[i+1][j-1]
// i.e. result of s[(i+1)...(j-1)]
dp[i][j] = dp[i+1][j-1];
// Answer array, ans[i] contain
// minimum cut needed for s[0...i]
ans = Array of size n
// Iterate from i = 1 to i = n-1;
For (i = 1 To i = n - 1)
// If s[0...i] is palindrome,
// no cut is needed.
If (dp[0][i])
ans[i] = 0
Else
// Initialize min with very large value.
min = Infinity
For (j = i To j = 0)
// If s[j...i] is a plaindrome
If(dp[j][i])
// Update min
min = min (min, ans[j - 1]);
// Put ans = 1 + min, 1 denotes the current cut.
ans[i] = 1 + min;
// Return ans[n-1].
Return ans[n - 1];
function end
Ja va Implementation
public class Main{
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
static int minimumCut (char[] s, int n){
// Table to store palindrome information.
// dp[i][j] = true means, s[i...j] is plaindrome.
boolean dp[][] = new boolean[n][n];
// Iterate from gap = 0 to gap = n-1
for (int gap = 0; gap < n; gap++){
// Iterate from i = 0, j = g to j = n-1
for (int i=0, j = gap; j < n; j++, i++){
// If gap is 0.
if (gap == 0)
dp[i][j] = true;
// Else if gap is 1
else if (gap == 1)
dp[i][j] = (s[i] == s[j]);
// Otherwise, if gap not equal to 0 or 1
// and s[i] = s[j].
else if (s[i] == s[j])
// Set dp[i][j] equal to dp[i+1][j-1]
// i.e. result of s[(i+1)...(j-1)]
dp[i][j] = dp[i+1][j-1];
}
}
// Answer array, ans[i] contain
// minimum cut needed for s[0...i]
int ans[] = new int[n];
// Iterate from i = 1 to i = n-1;
for (int i = 1; i < n; i++){
// If s[0...i] is palindrome,
// no cut is needed.
if (dp[0][i])
ans[i] = 0;
else{
// Initialize min with very large value.
int min = Integer.MAX_VALUE;
for (int j = i; j > 0; j--){
// If s[j...i] is a plaindrome
if(dp[j][i])
// Update min
min = Math.min (min, ans[j - 1]);
}
// Put ans = 1 + min, 1 denotes the current cut.
ans[i] = 1 + min;
}
}
// Return ans[n-1].
return ans[n - 1];
}
// Main function
public static void main (String args[]){
String s = "abaaab";
int count = minimumCut(s.toCharArray(), s.length());
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abccba";
count = minimumCut(s.toCharArray(), s.length());
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
s = "abcda";
count = minimumCut(s.toCharArray(), s.length());
System.out.println("Minimum cuts to partiton " +
s + " is " + count);
}
}
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
// Function to find minimum cut for
// palindrome partitoning of s.
// Initially low = 0, high = |s| - 1
int minimumCut (string s, int n){
// Table to store palindrome information.
// dp[i][j] = true means, s[i...j] is plaindrome.
bool dp[n][n];
// Make all its values to be false.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j] = false;
// Iterate from gap = 0 to gap = n-1
for (int gap = 0; gap < n; gap++){
// Iterate from i = 0, j = g to j = n-1
for (int i=0, j = gap; j < n; j++, i++){
// If gap is 0.
if (gap == 0)
dp[i][j] = true;
// Else if gap is 1
else if (gap == 1)
dp[i][j] = (s[i] == s[j]);
// Otherwise, if gap not equal to 0 or 1
// and s[i] = s[j].
else if (s[i] == s[j])
// Set dp[i][j] equal to dp[i+1][j-1]
// i.e. result of s[(i+1)...(j-1)]
dp[i][j] = dp[i+1][j-1];
}
}
// Answer array, ans[i] contain
// minimum cut needed for s[0...i]
int ans[n];
for(int i = 0; i < n; i++)
ans[i] = 0;
// Iterate from i = 1 to i = n-1;
for (int i = 1; i < n; i++){
// If s[0...i] is palindrome,
// no cut is needed.
if (dp[0][i])
ans[i] = 0;
else{
// Initialize min with very large value.
int Min = INT_MAX;
for (int j = i; j > 0; j--){
// If s[j...i] is a plaindrome
if(dp[j][i])
// Update min
Min = min(Min, ans[j - 1]);
}
// Put ans = 1 + min, 1 denotes the current cut.
ans[i] = 1 + Min;
}
}
// Return ans[n-1].
return ans[n - 1];
}
// Main function
int main(){
string s = "abaaab";
int count = minimumCut(s, s.length());
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abccba";
count = minimumCut(s, s.length());
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
s = "abcda";
count = minimumCut(s, s.length());
cout << "Minimum cut to partition " << s
<< " is " << count << endl;
}
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Python Implementation
# Function to find minimum cut for
# palindrome partitoning of s.
# Initially low = 0, high = |s| - 1
def minimumCut (s, n):
# Table to store palindrome information.
# dp[i][j] = true means, s[i...j] is plaindrome.
dp = [[False for i in range(n)] for j in range(n)]
# Iterate from gap = 0 to gap = n-1
for gap in range(n):
# Iterate from i = 0, j = g to j = n-1
for i, j in zip(range(n), range(gap, n)):
# If gap is 0.
if (gap == 0):
dp[i][j] = True
# Else if gap is 1
elif (gap == 1):
dp[i][j] = (s[i] == s[j])
# Otherwise, if gap not equal to 0 or 1
# and s[i] = s[j].
elif (s[i] == s[j]):
# Set dp[i][j] equal to dp[i+1][j-1]
# i.e. result of s[(i+1)...(j-1)]
dp[i][j] = dp[i+1][j-1]
# Answer array, ans[i] contain
# minimum cut needed for s[0...i]
ans = [0 for i in range(n)]
# Iterate from i = 1 to i = n-1;
for i in range (1, n):
# If s[0...i] is palindrome,
# no cut is needed.
if (dp[0][i]):
ans[i] = 0
else:
# Initialize min with very large value.
Min = 99999999
for j in range(i, 0, -1):
# If s[j...i] is a plaindrome
if(dp[j][i]):
# Update min
Min = min(Min, ans[j - 1])
# Put ans = 1 + min, 1 denotes the current cut.
ans[i] = 1 + Min
# Return ans[n-1].
return ans[n - 1]
# Driver code
s = "abaaab"
count = minimumCut(s, len(s))
print ("Minmum cuts to partiton",
s, "is", count)
s = "abccba"
count = minimumCut(s, len(s))
print ("Minmum cuts to partiton",
s, "is", count)
s = "abcda"
count = minimumCut(s, len(s))
print ("Minmum cuts to partiton",
s, "is", count)
Output
Minimum cut to partition abaaab is 1
Minimum cut to partition abccba is 0
Minimum cut to partition abcda is 4
Complexity Analysis
- Time Complexity – In part 1 of the algorithm we are using two nested loops, each of which is running for O(n) times in the worst case. Also in part 2, there are two nested loops each of which is running for O(n) times. Hence the overall time complexity is O(n2).
- Space Complexity – Since we are using a 2-D array of dimensions n×nn×n to store the results. Hence the space complexity is O(n2).
Conclusion
- Palindrome Partitioning is a way to split a string into contiguous segments such that each segment is a palindrome.
- Minimum cuts required to obtain palindrome partitioning can be found in O(n∗2n) time using the recursive approach.
- The time complexity of the solution can be brought down to O(n2) either by using memoization, or using Bottom-up dynamic programming.
