• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Problem Statement:


Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:
Input: s = "a"
Output: 0

Example 3:
Input: s = "ab"
Output: 1

Solution:



This problem is a use case for both All possible Cuts in all possible Intervals for the Last Operation approach and 1-String DP. So it is imperative that you have a strong grasp of both the concepts. We would be using the templates discussed in both the aforementioned chapters in solving this problem.

Java Code:




This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python Code:




This is a Premium content.
Please subscribe to Algorithms course to access the code.





Space Optimization


We can use 1D array dp[] instead of 2D for computing dp values of the minimum cuts required. dp[i] = minimum number of cuts for palindrome partitioning of s[0...(i - 1], where s[0...(n - 1)] is the given original string.

Notice that the substring on the right side of the last cut is always palindrome. So we use the already computed dp value for the substring on the left of the last cut and add one to it. Why ? DP value for the substring on the left of the CUT gives the minimum number of cuts required for the substring on the LEFT of the CUT. The substring on the RIGHT of the CUT is a palindrome, so no cut required there since we are interested in minimum number of cuts.

Therefore, the total number of CUTS = minimum number of cuts required in substring left of the CUT + (the CUT itself)
or, Total number of CUTS = minimum number of cuts required in substring left of the CUT + 1

You might ask why we are looking for right-most palindrome substring and not the left-most ? Notice how dp[i] gives the minimum cuts for palindrome partitioning of str[0...(i - 1)], so we get the dp value for the prefix and not the suffix. So we need to find the palindromic suffix in order to use the sub-structures from dp[], and suffixes are the right-most parts of strings.

Java Code:




This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python Code:




This is a Premium content.
Please subscribe to Algorithms course to access the code.





The space optimization technique that you just saw is a very simple but powerful optimization technique. Please take some time to have a good grasp of it. This space optimization technique can be used in various different types of problems. This kind of optimization is what I call "taking advantage of the information given in the problem statement". These are the subtle ways of optimization that you can achieve just by have a good sense of observation and an open mind to come up with up with more than one solution.

The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave