Let's now get started with another famous coding interview question, which is called palindrome partitioning.
So the question says given a string s partition s such that every substring of the partition is a palindrome,
return all possible palindrome partitioning of S, and we're given an example.
If the input string is a a, b a, then these are the possible partitionings.
So notice over here this partitioning over here is achieved if we partition the given string in this
manner.
So that's this over here.
And then the second partitioning over here is obtained by partitioning the given string in this manner.
And then we get this partitioning over here by partitioning a a B a.
In this manner.
And in each of these cases the criteria mentioned in the question is satisfied.
So all of these are palindromes.
So that's the criteria given in the question.
Now partitioning it in this way for example, would be not valid because notice this over here is not
a palindrome.
So this is the question at hand.
I'm sure we have understood the question.
And remember always before you start solving a coding interview question which is given to you, remember
to ask any clarifying questions that you may want to ask.
A possible question that you may want to ask for this question is, do I need to treat small case and
upper case letters differently?
And let's say the interviewer replies, you will only be given a string that consists of lower case
letters.
So we have understood the question, and we have asked any clarifying questions that we wanted to ask.
Let's now proceed and write a few test cases.
And remember, it's always a good practice to work on this together with the interviewer.
You can come up with test cases along with the interviewer, and this will ensure that both of you are
on the same page.
Now we have a test case which was given to us as an example for the question.
That was the case where a, a, b a was the input string.
And we have seen that these are the three ways of partitioning a, a BA in a way that all the substrings
after we partition the string are palindromes themselves.
Now, if you're given a string with just one character, then the required output would be this.
Again, notice that it's an array of arrays.
And over here again, because there is just one way of partitioning this, we just have one element
in this array.
Another input that we could consider is let's say the array which is given to us is a a.
If this is the input array, the required output would be a a.
So this is one partitioning.
And then you could have a a together right.
So you would have two ways of partitioning the characters over here.
And notice that all of these are palindromes.