# Palindrome Partitioning Problem

## Problem Statement

Given a string s, partition s such that every partition of s is a palindrome. Find the minimum number of cuts to form a palindromic partition of s.

Palindrome: A string is called a palindrome when it is read the same way both forwards and backward.

Sample Test Cases

Input 1: s = “Coffee”
Output 1: 3
Explanation 1:

From the picture above, it is evident that a minimum of 3 partitions is needed to make a palindromic partition of s.

Input 2: s = “ababbbabbababa”
Output 2: 3
Explanation 2:

From the picture above, it is evident that 3 cuts are needed for this string.

## Naive Approach

We can solve this problem naively, using a recursive backtracking-based algorithm. Observe that if the string is a palindrome, we will need 0 cuts for it (this will be the base case for our recursion). Else, we can try to put cuts at all possible positions in the string and try to calculate the number of cuts needed to make a valid palindromic partitioning over all possible combinations of cuts and return the minimum among them.

### C++ Implementation

```int checkPalindrome(string & s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return 0;
}
start++;
end--;
}
return 1;
}
int minimumCuts(string & s, int i, int j) {
if (checkPalindrome(s, i, j) || i >= j) {
return 0;
}
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
countCuts += 1;
}
}
int getMinCuts(string s) {
int n = s.length();
return minimumCuts(s, 0, n - 1);
}```

### Java Implementation

```public static int checkPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return 0;
}
start++;
end--;
}
return 1;
}
public static int minimumCuts(String s, int i, int j) {
if (checkPalindrome(s, i, j) == 1 || i >= j) {
return 0;
}
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
countCuts += 1;
}
}
public static int getMinCuts(String s) {
int n = s.length();
return minimumCuts(s, 0, n - 1);
}```

### Python Implementation

```def checkPalindrome(s, start, end):
while start < end:
if s[start] != s[end]:
return 0
start += 1
end -= 1
return 1

def minimumCuts(s, i, j):
if checkPalindrome(s, i, j) or i >= j:
return 0
countCuts = -1
for k in range(i, j):
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j)
countCuts += 1

def getMinCuts(s):
n = len(s)```

### Complexity Analysis

• Time Complexity: Exponential.
• Space Complexity: O(1) if recursion stack space is excluded.

## Memoization Based Approach

Consider the case when we partition a string from say [0, i], [i + 1, j], [j + 1, n] and we know the cost for each of these substrings. Now, if we want to compute the cost for a combination of cuts such the substrings corresponds to [0, i], [i + 1, l], [l + 1, j], [j + 1, n], then in our brute force method we will again compute the costs for the substrings [0, i] and [j + 1, n].

So, we can observe that there will be multiple such redundant function calls. To prevent these redundant function calls, we can memoize/cache the results of these function calls in some containers, and recompute them in O(1) when needed. This will reduce our computational complexity from exponential to polynomial time at the trade-off of some extra space.

### C++ Code

```int checkPalindrome(string & s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return 0;
}
start++;
end--;
}
return 1;
}
int minimumCuts(string & s, int i, int j, vector < vector < int >> & dp) {
if (checkPalindrome(s, i, j) || i >= j) {
return dp[i][j] = 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
countCuts += 1;
}
return dp[i][j];
}
int getMinCuts(string s) {
int n = s.length();
vector < vector < int >> dp(n + 1, vector < int > (n + 1, -1));
return minimumCuts(s, 0, n - 1, dp);
}```

### Java Code

```public static int checkPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return 0;
}
start++;
end--;
}
return 1;
}
public static int minimumCuts(String s, int i, int j, int[][] dp) {
if (checkPalindrome(s, i, j) == 1 || i >= j) {
dp[i][j] = 0;
return dp[i][j];
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
countCuts += 1;
}
return dp[i][j];
}
public static int getMinCuts(String s) {
int n = s.length();
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], -1);
}
return minimumCuts(s, 0, n - 1, dp);
}```

### Python Code

```def checkPalindrome(s, start, end):
while start < end:
if s[start] != s[end]:
return 0
start += 1
end -= 1
return 1

def minimumCuts(s, i, j, dp):
if checkPalindrome(s, i, j) or i >= j:
dp[i][j] = 0
return dp[i][j]
if dp[i][j] != -1:
return dp[i][j]
countCuts = -1
for k in range(i, j):
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp)
countCuts += 1
return dp[i][j]

def getMinCuts(s):
n = len(s)
dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
return minimumCuts(s, 0, n - 1, dp)```

### Complexity Analysis

• Time Complexity: O(n2)
• Space Complexity: O(n2)

## Iterative DP Based Approach

We can solve this problem by using Dynamic Programming to compute the results of the overlapping problems shown in the previous example under memoization and storing them in a DP Table. To solve this problem effectively, we will need two DP arrays, as follows,

• DP[i][j] = True if the substring from [i, j] is a palindrome, else False.
• DpCut[i] = Minimum number of cuts required for prefix from 0 to i.

Using these 2 DP arrays, we can compute the answer for the entire string, and the result will be stored in DpCut[string.length – 1]. If we compute the DP array beforehand and then using its results compute the DpCut array, we can further reduce the time complexity of the problem to Quadratic Asymptotics.

Check the implementation for a better understanding of the approach:

### C++ Code – DP Approach

```int getMinCuts(string & s) {
int n = s.length();
vector < int > DpCut(n);
int dp[n][n];
memset(dp, false, sizeof(dp));
for (int i = 0; i < n; i++) {
int minimumCuts = i;
for (int j = 0; j <= i; j++) {
if (s[i] == s[j]) {
if (((i < (j + 2) || dp[j + 1][i - 1]))) {
dp[j][i] = true;
if (j == 0) {
minimumCuts = 0;
} else {
minimumCuts = min(minimumCuts, DpCut[j - 1] + 1);
}
}
}
}
DpCut[i] = minimumCuts;
}
return DpCut[n - 1];
}```

### Java Code – DP Approach

```public static int getMinCuts(String s) {
int n = s.length();
int[] DpCut = new int[n];
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], false);
}
for (int i = 0; i < n; i++) {
int minimumCuts = i;
for (int j = 0; j <= i; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i < (j + 2) || dp[j + 1][i - 1]) {
dp[j][i] = true;
if (j == 0) {
minimumCuts = 0;
} else {
minimumCuts = Math.min(minimumCuts, DpCut[j - 1] + 1);
}
}
}
}
DpCut[i] = minimumCuts;
}
return DpCut[n - 1];
}```

### Python Code – DP Approach

```def getMinCuts(s):
n = len(s)
cutDp =  * n
dp = [[False for i in range(n)] for j in range(n)]
for i in range(n):
minimumCuts = i
for j in range(i + 1):
if s[i] == s[j]:
if i < (j + 2) or dp[j + 1][i - 1]:
dp[j][i] = True
if j == 0:
minimumCuts = 0
else:
minimumCuts = min(minimumCuts, cutDp[j - 1] + 1)
cutDp[i] = minimumCuts
return cutDp[n - 1]```

### Complexity Analysis

• Time Complexity: O(n2)
• Space Complexity: O(n2)

## FAQs

Q. How to identify that a problem can be solved by Dynamic Programming?
A. A problem can be solved using Dynamic Programming if it contains some Optimal Substructure and Overlapping Subproblems.

Q. Which of the above approaches is expected to be the fastest?
A. The iterative DP approach is expected to be faster in practice than the Recursive Memoization approach because repeated function calls often bring with them some associated overhead which takes some extra time.

##### Previous Post ## Trailing Zeroes in Factorial

##### Next Post 