# Palindrome Partitioning

Difficulty Level Medium
Backtracking Depth First Search Dynamic ProgrammingViews 1375

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.

## 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.

References

Translate »