🙏

জয়  শ্রী  রাম

🕉

---

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:

Login to Access Content

Python Code:

Login to Access Content

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:

Login to Access Content

Python Code:

Login to Access Content




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.

Instructor: