New update is available. Click here to update.

Last Updated: 11 Nov, 2020

Hard

```
Input: 'str' = "aaccb"
Output: 2
Explanation: We can make a valid partition like aa | cc | b.
```

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

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

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

Approaches

- 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