Palindrome Partitioning ll

New update is available. Click here to update.

Last Updated: 11 Nov, 2020

Palindrome Partitioning ll

Hard

Solve now

Problem statement

You are given a string 'str' of length 'n'.

Find the minimum number of partitions in the string so that no partition is empty and every partitioned substring is a palindrome.

Example :

Input: 'str' = "aaccb"

Output: 2

Explanation: We can make a valid partition like aa | cc | b.

Input format :

The first line contains the string 'str', the string to be partitioned.

Output Format :

Print the minimum number of cuts to be done so that each partitioned substring is a palindrome.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Solve now

Approaches

01Approach

This is a recursive approach.
We can break the problem into a set of related subproblems which partition the given string in such a way that yields the lowest possible total cuts.
In each recursive function call, we divide the string into 2 subsequences of all possible sizes.
Let ‘i’, ‘j’ be the starting and ending indices of a substring respectively.
If ‘i’ is equal to ‘j’ or str[‘i’.....’j’] is a palindrome, we return 0.
Otherwise, we start a loop with variable ‘k’ from starting index of string ‘i’ and ending index of string ‘j’ - 1 and then recursively call the function for the substring with starting index ‘i’ and ending index ‘j’ to find the minimum cuts in each subsequence.
Do this for all possible positions where we can cut the string and take the minimum over all of them.
In the end, the recursive function would return the minimum number of partitions needed for the complete string.

Solve now

02Approach

We can observe that the problem has optimal substructure and overlapping subproblems and hence can be solved using dynamic programming. The idea is to store the results of subproblems so that we do not have to re-compute them when they are needed.

Below is an approach in which smaller subproblems are stored first, which are used to solve the larger sub-problems. The below approach computes two 2-Dimensional arrays 'isPalindrome[][]' and 'cuts[][]' where 'isPalindrome[i][j]' stores if a substring with starting index ‘i’ and ending index ‘j’ is a palindrome or not. (isPalindrome[i][i] is true as every string of length 1 is a palindrome)

cuts[i][j] stores the minimum number of cuts needed for a substring with starting index ‘i’ and ending index ‘j’.

Run a loop where 2 <= l <= n. Consider ‘l’ as the length of the substring.
For each substring of length ‘l’ set different possible starting indices ‘i’ where ‘i’ ranges from 0 to L-1 and calculate 'cuts[i][j]' where ‘j = i + l - 1’, i.e. the last index of the string with starting index ‘i’ and length ‘l’ and 'cuts[i][j]' is the minimum cuts needed for the string ‘str[ i…..j]’.

We can optimise it for the following cases:

If ‘l’ is equal to 2, we just need to compare 2 characters. Else we need to check two corner characters and the value of ‘isPalindrome[i + 1][j - 1]’
If ‘str[ i….j]’ is palindrome then ‘cuts[i][j] = 0’
Otherwise, we take a variable ‘k’ where ‘i’ <= k <= ’j’ and make a cut at every kth location to find the number of cuts. We repeat this at every possible location starting from ‘i’ to ‘j’, and get a minimum cost cut. And store it at cuts[ i ][ j ].
Lastly, return ‘cuts[0][n - 1]’ stores the minimum number of cuts needed.

Solve now

03Approach

In the previous approach, we calculated the minimum cut while finding all palindromic substring. If we find all palindromic substrings first and then calculate the minimum cut, the solution would optimize.

We can do that in the following way:

Compute one 2 Dimensional arrays 'isPalindrome[][]' and an array 'cuts[]' where 'isPalindrome[i][j]' stores if a substring with starting index ‘i’ and ending index ‘j’ is a palindrome or not.
Mark isPalindrome[i][i] true as every substring of length 1 is a palindrome.cuts[i] is the minimum number of cuts needed for a palindrome partitioning of substring str[0..i]. Now, find all the palindromic substrings in the given string for each length ‘l’ and for every starting index ‘i’. In the following way:
If the value of ‘l’ is 2 we just compare the 2 characters.
Otherwise, we check the first and last character of the substring and also if isPalindrome[i + 1][j - 1] is true. If yes, we mark the current substring as a palindrome.

Now that we know all the substrings which are Palindromes, We can efficiently find the minimum cuts in the following way:

Let cuts[i] is the minimum number of cuts needed for a palindrome partitioning of substring str[0..i]
If isPalindrome[0][i] is true we say cuts[i]=0.
Otherwise, we first initialize the value of cuts[i] to be infinite.
Then for each ‘i’ we take a variable’ j’ and initialize it to 0.
Then we loop through j such that 0 <= j < i and find update cuts[i], if 1 + cuts[j] is less than the current value of cuts[i] i.e we find a better way of partitioning the substring str[0...i] with lesser number of cuts.
We add an extra 1 because the substring is not palindrome we need to make a cut.
Otherwise cuts[i] = cuts[j] + 1 for all j < i and if str[j + 1...i] is a palindrome
Finally, our answer lies at cuts[n - 1] which is the final answer

Solve now