Palindrome Partitioning ll

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion. The idea is to use recursion to reduce the big problem into several small subproblems.

Here is the algorithm :

1. We will call a recursive function ‘minimumCutsHelper’ that takes the string, the starting index, and the ending index of the string. This function will generate all possible partitions and will decide the minimum possible cuts required.
2. The algorithm for the helper function will be as follows and ‘START’ is the starting index, ‘END’ is the ending index and ‘STR’ is the given string.
   int minimumCutsHelper(STR, start, end):
   • If ‘START’ = ‘END’, the string contains only 1 character which will definitely be a palindrome. Thus, return 0.
   • If ‘STR[ START to END ]’ is a palindrome, no partition is needed, return 0.
   • Create an ‘ANSWER’ variable to store the final answer.
   • Now, we calculate ‘ANSWER’ for every possible partition,
   • For ‘k’ in the range start to ‘END’ - 1:
     • Call minimumCutsHelper(STR, start, k) + 1 + minimumCutsHelper(STR, k + 1, end) and store it in a variable say ‘CURRENTCUTS’.
     • Update answer by ‘CURRENTCUTS’ if ‘CURRENTCUTS’ is less than the answer.
   • Return ‘ANSWER’.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. 

Lets understand by an example:

Suppose we have ‘STR’ as “abc” 

The below figure shows some of the recursive calls made for the given problem. 

As we can see, some subproblems are called multiple times. 

The same subproblems are shown by the same color.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.
 

Here is the algorithm:

1. Create a 2D ‘LOOKUP’ matrix of size ‘N’ * ‘N’. Lookup matrix stores the solutions to the subproblems where ‘lookUp[i][j]’ denotes the minimum cuts for palindromic partitions needed for ‘STR[ i to j ]’.
2. Initialize the matrix by -1.
3. Now, we will call a recursive function ‘minimumCutsHelper’ that takes the sting, the starting index, and the ending index of the string. This function will generate all possible partitions and will decide the minimum possible cuts.
4. The algorithm for the helper function will be as follows and ‘START’ is the starting index, ‘END’ is the ending index and ‘STR’ is the given string.
   int minimumCutsHelper(STR, start, end, lookUp):
   • If ‘START’ = ‘END’, return 0.
   • If ‘LOOKUP[START][END]’ is not -1, we already have the answer, return ‘LOOKUP[START][END]’.
   • If ‘START’ = ‘END’, the string contains only 1 character which will definitely be a palindrome. Thus, update ‘LOOKUP[START][END]’ with 0 and return 0.
   • If ‘STR[ START to END ]’ is a palindrome, no partition is needed, update ‘LOOKUP[START][END]’ as 0 and return 0.
   • Create an ‘ANSWER’ variable to store the final answer.
   • Now, we calculate ‘ANSWER’ for every possible partition.
     • For ‘k’ in the range ‘START’ to ‘END’ - 1:
       • Call minimumCutsHelper(STR, start, k, lookUp) + 1 + minimumCutsHelper(STR, k + 1, end, lookUp) and store it in a variable say ‘CURRENTCUTS’.
       • Update answer by ‘CURRENTCUTS’ if ‘CURRENTCUTS’ is less than the answer.
5. Store the ‘ANSWER’ in the lookup table as ‘LOOKUP[START][END]’ = ‘ANSWER’.
6. Return the ‘ANSWER’.

This problem can be solved using Dynamic Programming. Follows the steps below to solve this problem:

Here is the algorithm: 

1. The idea is to create a 2-D array ‘CUTS’ of size ‘N’ * ‘N’.
2. Initially, all the elements of the ‘COST’ matrix will be the maximum positive number.
3. Now, the value ‘CUTS[i][j]’ denotes the minimum number of cuts required for palindromic partitioning of substring ‘STR[i...j]’.
4. If the length of the string is 1, it is already a palindrome and 0 cuts are required.
5. The detailed algorithm to fill the ‘CUTS’ matrix is as follows:
6. L1: Run a loop from ‘SIZE’ = 2 to ‘N’ to try all the possible substrings.
7. L2: Run a loop from ‘i’ = 0 to current length to select the ending index of the substring. The ending index ‘j’ of the substring is (‘i’ + ‘SIZE’ - 1).
8. L3: Run a loop to check whether the considered substring is a palindrome or not.
   • If yes, we don't require any cut for the current substring and update the ‘CUTS’ matrix as ‘CUTS[i][j]’ = 0.
   • Else, run a loop to make a cut at every possible location of the substring and get the minimum cost cut.
   • For ‘k’ in range ‘i’ to ‘j’:
     • Make a cut a kth position, and update the ‘CUTS’ matrix as ‘CUTS[i][j]’ = min(‘CUTS[i][j]’, ‘CUTS[i][k]’ + ‘CUTS[i][k + 1]’ + 1).
     • Note that L1, L2, and L3 will be three nested loops.
9. Return ‘CUTS[0][N-1]’, the final minimum number of cuts required to partitioning the string ‘STR' from index 0 to ‘N’ - 1 (including).

In the previous approach, we were checking for the palindrome or we were making the cut at every possible location. This step resulted in an additional time consumption of the order O(N), resulting in the time complexity of O((N ^ 2) * N) = O(N ^ 3). Instead of checking for the palindrome in O(N) time, we can check it in O(1) time.  

Here is the algorithm:

1. Create a 2-D boolean array ‘isPalindrome’ of size ‘N’ * ‘N’. 

2. The value ‘isPalindrome[i][j]’ denotes whether the substring ‘STR[i...j]’ is a palindrome or not. 

3. Now, to calculate ‘isPalindrome[i][j]’, just check ‘isPalindrome[i + 1][j - 1]’ and the corner characters, ‘STR[i]’ and ‘STR[j]’. 

‘isPalindrome[i][j]’ will be “True” if ‘STR[i]’ is equal to ‘STR[j]’ and ‘isPalindrome[i + 1][j - 1]’ is “true”. Else, it will be “False”. 

The final time complexity can be reduced from O(N ^ 3) to O(N ^ 2), by precomputing the ‘isPalindromic’ matrix in O(N ^ 2) and then filling the ‘CUTS’ array in O(N ^ 2). 

Create a 1-D array ‘CUTS’ of size (N), where ‘CUTS[i]’ stores the minimum number of cuts required for palindromic partitioning of substring ‘STR[0..i]’.

Algorithm to fill the ‘CUTS’ array:

1. Initially, all the elements of the ‘COST’ matrix will be the maximum positive number.
2. L1: Run a loop from ‘i’ = 0 to ‘N’:

• If the substring ‘STR[0...i]’ is palindrome, we don’t require any cut. Thus, ‘CUTS[0][i]’ = 0.
• L2: Else, run a loop from ‘j’ = 0 to ‘i’:
  • If the substring ‘STR[j + 1...i]’ is a palindrome and the cuts required for palindromic partitioning of substring ‘STR[0...j]’  + 1 is less than the cuts required for palindromic partitioning of substring ‘STR[0...i]’, update cuts matrix as ‘CUTS[i]’ = ‘CUTS[j]’ + 1.
• Return ‘CUTS[N-1]’, the final minimum number of cuts required to partitioning the string ‘STR’ from index 0 to ‘N’ - 1 (including).

Note that L1 and L2 are two nested loops.