Palindrome Partitioning ll

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

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.

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