Palindrome Partitioning is a DP problem. In this problem, Given a string S. Partition S such that every substring of the partition is a palindrome. We need to print the minimum cuts needed for a palindrome partitioning of S.
Table of Contents
Input Format
Only a single line containing string S.
Output Format
Print the single integer value which is minimum cuts needed for a palindrome partitioning of S.
Constraints
- 1<=|s|<=1000.
Example Input: abcdefedc
Example Output: 2
Explanation For Palindrome Partitioning
Here we divide the string into 3 substrings using 2 cuts. The substrings are “a”, “b”, “cdefedc”. Here we use a 2D matrix for storing the information which tells us whether a substring is a palindrome or not. If DP[i][j] is 1 that means substring s(i,j) is a palindrome else DP[i][j]=0. Now for the count of minimum cuts, we need an array that stores the information about the previous cut from [0-i].
If DP[0][1] is 1 then cuts[i] =0 else, check that substring from j+1 to i is a palindrome and cuts[j]+1 is minimum possible where 0<=j<i.
After this, we need to update the minimum cuts from 0 to i by the use of minimum cuts possible which we find for rest substrings.
Algorithm For Palindrome Partitioning
Algorithm:
Step:1 Set dp[n][n]=0.
Step:2 Set dp[i][i]=1 for all i where 0<=i<n.This is for all substrings of length 1 are palindrome.
Step:3 For all values of i where 0<=i<n-1, we check if s[i]=s[i+1] then dp[i][i+1]=1. This is for all substrings of length 2 are palindrome.
Step:4 For rest of the other length substring:
for i in range 3 to n:
for j in range 0 to n-i:
last=j+i-1.
if s[j]=s[last] then:
if dp[j+1][last-1] then:
dp[j][last]=1;
Step:5 Count the minimum cuts required. Make a array cuts of size n and set all its value as 1e9.
for i in range 0 to n-1:
set calc as 1e9.
if dp[0][i] is 1 then:
cuts[i]=0;
else:
for j in range 0 to i-1:
if dp[j+1][i]=1 and calc greater than (cuts[j]+1) then:
set calc=cuts[j]+1.
set cuts[i]=calc;
Step:6 Print the value of cuts[n-1].
Implementation For Palindrome Partitioning
/*C++ Implementation of Palindrome Partitioning using DP approch*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*input string*/
string s;
cin>>s;
int n=s.length();
int dp[n+1][n+1];
/*set 0 to all cell of dp matrix.*/
memset(dp,0,sizeof(dp));
/*for all 1 length substrings which are palindrome.*/
for(int i=0;i<n;i++)
{
dp[i][i]=1;
}
/*for all 2 length substrings which are palindrome.*/
for(int i=0;i<n-1;i++)
{
if(s[i]==s[i+1])
{
dp[i][i+1]=1;
}
}
/*for all substrings greater than length 2 which are palindrome.*/
for(int i=3;i<=n;i++)
{
for(int j=0;j<n-i+1;j++)
{
int last=j+i-1;
/*first and last char must be the same.*/
if(s[j]==s[last])
{
/*substring s[i+1 to j-1] must be palindrome.*/
if(dp[j+1][last-1])
{
dp[j][last]=1;
}
}
}
}
int cuts[n];
/*set maximum value(1e9) to each cell of cuts array*/
memset(cuts,1e9,sizeof(cuts));
/*calculating minimum cuts*/
for(int i=0;i<n;i++)
{
int calc=1e9;
/*if substring from 0 to i is palindrome*/
if(dp[0][i])
{
cuts[i]=0;
}
else/*others casec*/
{
/*check for all index less than i to get the minimum cuts for j to i*/
for(int j=0;j<i;j++)
{
/*if substring from j+1 to i is a palindrome */
if((dp[j+1][i])&&calc>cuts[j]+1)
{
calc=cuts[j]+1;
}
}
cuts[i]=calc;
}
}
/*print the minimum cut required value*/
cout<<cuts[n-1]<<endl;
return 0;
}ssadafudedufadddd
3
Time Complexity
O(N*N) where N is the length of the string. When we update the values in the dp matrix then we need to visit for all possible pairs in which nested for loop we use.
Space Complexity
O(N*N) where N is the length of the string. We create a 2d DP matrix of order N*N to store the values 0,1 to check whether a substring is a palindrome or not.