Given a string "str", the task is to determine fewest cuts needed to perform palindrome partitioning on it.
A partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome.
A palindrome string is a string that reads the same backward as forward.
Input: str = "ababbbabbababa"
Output: 3
Input: str = "aaabba"
Output: 1
Input: str = "abc"
Output: 2
Solutions
Method 1: Recursion
This Palindrome Partitioning problem is a variation of Matrix Chain Multiplication.
Like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.
The idea is to consider the sub-array from "s" to "e" in each recursion, where "s" is the first element and "e" is the last element.
Try to put "k" in different places in each recur and get the minimum cost of left and right sub-arrays recursively, then add left-cost, right-cost, and cost of current cut i.e. "1".
Use an inner "for" loop for this purpose.
In each recur, we will get multiple values for "minCuts" because we are getting one minCuts for each inner loop run.
In each recur, we need to return the minimum of all "minCuts" we got from putting k in different places using the inner loop.
That means, the recur will define which part of the array the logic should work on, and the inner loop will define a different position of "k" for each sub-array.
Now for each recur, the position of k will start from "s" to "e-1".
Base Condition: If a string is of length "1" or if its is a palindrome, then minimum "0" cuts are needed.
Complexity
The time complexity of this solution is exponential O(2^n).
In addition, O(2^n) auxiliary space was used by the recursion stack.
Method 2: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "s" and "e" changes, so we can store and reuse the result of a function(..s,e..) call using a "n+1*n+1" array.
The array will store a particular state (..s,e..) if we get it the first time.
Now, if we come across the same state (..s,e..) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n^2).
In addition, O(n^2) auxiliary space was used by the table.