Find minimum cuts needed for palindromic partition of a string

Given a string, find minimum cuts needed to partition it such that each partition is a palindrome.

 

For example,

 

1. BABABCBADCD – The minimum cuts required are 2 as BAB|ABCBA|DCD

2. ABCBA – The minimum cuts required are 0 as ABCBA is already a palindrome

3. ABCD – The minimum cuts required are 3 as A|B|C|D

 


 

We can break the problem into a set of related subproblems which partition the given string in such a way that yields the lowest total cuts. Below is the recursive algorithm to find the minimum cuts –

  1. Separate the given string into two subsequences.
     
  2. Recursively find the minimum cuts of required in each subsequence.
     
  3. Do this for each possible position at which the string can be cut, and take the minimum over all of them.

For example, if we have string ABCB, we compute the cuts required to find each of A|BCB, AB|CB, and ABC|B, making recursive calls to find the minimum cuts to compute BCB, AB, CB, and ABC choose the best one.

C++

Download   Run Code

Output:

The minimum cuts required are 2

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

 


 

The problem has an optimal substructure and also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. As both optimal substructure and overlapping subproblems properties of dynamic programming are satisfied, we can save subproblem solutions in memory rather than computed again and again.

We can further optimize above recursive solution by removing isPalindrome() function which takes linear time in worst case. Instead, the idea is to pre-process the string and maintain a lookup table to check if sub-string starting at index i and ending at index j is a palindrome or not in constant time.

C++

Download   Run Code

Output:

The minimum cuts required are 2

The time complexity of above solution is O(n3) and auxiliary space used by the program is O(n2).

 


 

 
We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. It has the “less” asymptotic run-time and requires no recursion. The approach is illustrated below –

C++

Download   Run Code

Output:

The minimum cuts required are 4

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz