Palindrome Partitioning

Problem Statement

Partitioning of any string $s$ is considered to be palindrome partitioning if every substring of the partition is a palindrome.

In this problem, you have been given a string $s$ and you need to determine the fewest cuts needed for a palindrome partitioning of the given string.

Examples

Example 1

Input : abaaab
Output :

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

Explanation Since the string abccba is already a palindrome, hence no need to make any cut.

Example 3

Input : abcda
Output :

Explanation : The only possible way is to make cut at every possible position $i.e.$ a|b|c|d|a.

Constraints

• $1\leq |s| \leq 1000$
• All characters in $s$ 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 $s$ 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 $s$ of length $n$, 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

Java Implementation

Output

C++ Implementation

Output

Python Implementation

Output -

Complexity Analysis

• Time Complexity - There are $2^n$ 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\times 2^n)$.
• 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 $s$ of length $n$, 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.$ 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

Java Implementation

Output -

C++ Implementation

Output -

Pyhton Implementation

Output

Complexity Analysis

• Time Complexity - The time complexity of the above code is $O(n^3)$. Because using memoization we have reduced $O(2^n)$ to $O(n^2)$ (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(n^3)$.

• Space Complexity - Since we are using a 2-D array of dimensions $n\times n$ to store the results. Hence the space complexity is $O(n^2)$.

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 -

1. 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.
2. 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)].

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

Ja va Implementation

Output

C++ Implementation

Output

Python Implementation

Output

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(n^2)$.

• Space Complexity - Since we are using a 2-D array of dimensions $n\times n$ to store the results. Hence the space complexity is $O(n^2)$.