Welcome back.
Let's now get started with another interesting coding interview question, which is called Palindrome
Partitioning two.
The question reads 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 s will not be an empty string, and we are given an example.
Let's say the string given to us is a b, b.
Now the output required is equal to one, because the minimum number of cuts required to partition this
into sub strings in a manner that every substring is a palindrome is equal to one, which is this cut
over here.
Remember, you could do it also in this manner.
Like you could have a cut over here and a cut over here.
But then in this case you would need two cuts.
But we are asked to identify the minimum cuts required which is equal to one.
Now the question is pretty straightforward to understand.
And do remember to ask any clarifying questions you may want to ask when you are presented with a coding
interview question.
Now, a possible question that you could ask over here is do I need to treat uppercase and lowercase
letters differently?
And let's say the interviewer replies that you will only be given a string that consists of lowercase
characters.
So we have understood the question and we have asked any clarifying questions that we had.
Now let's proceed and write a few test cases.
Now we already were given an example.
If the input is AB, then the output expected is one, because you can partition this into sub strings
where every substring is a palindrome with just one cut over here.
Now, if the string which is given to you is just a or if it has just one character, then this itself
is a palindrome and therefore we do not need any cuts.
And if the string which is given to us is b a, we would need one cut.
Another test case is if the string is ab a, then we would not require any cut because ab a is a palindrome,
and if the string which is given to us is ab a CD.
Notice that you would need two cuts because this is a palindrome.
And then we have these two over here.
So the total number of cuts required is equal to two.
Now remember writing test cases is a very important step because it helps you think deeply about the
problem at hand.