1
00:00:00,820 --> 00:00:08,170
Let's now get started with another famous coding interview question, which is called palindrome partitioning.

2
00:00:08,590 --> 00:00:18,640
So the question says given a string s partition s such that every substring of the partition is a palindrome,

3
00:00:19,060 --> 00:00:25,390
return all possible palindrome partitioning of S, and we're given an example.

4
00:00:25,480 --> 00:00:31,900
If the input string is a a, b a, then these are the possible partitionings.

5
00:00:31,900 --> 00:00:38,860
So notice over here this partitioning over here is achieved if we partition the given string in this

6
00:00:38,860 --> 00:00:39,430
manner.

7
00:00:40,180 --> 00:00:41,650
So that's this over here.

8
00:00:41,650 --> 00:00:48,490
And then the second partitioning over here is obtained by partitioning the given string in this manner.

9
00:00:48,490 --> 00:00:53,620
And then we get this partitioning over here by partitioning a a B a.

10
00:00:53,620 --> 00:00:55,000
In this manner.

11
00:00:55,000 --> 00:01:00,700
And in each of these cases the criteria mentioned in the question is satisfied.

12
00:01:00,700 --> 00:01:03,670
So all of these are palindromes.

13
00:01:05,120 --> 00:01:07,850
So that's the criteria given in the question.

14
00:01:07,850 --> 00:01:15,740
Now partitioning it in this way for example, would be not valid because notice this over here is not

15
00:01:15,740 --> 00:01:16,640
a palindrome.

16
00:01:16,640 --> 00:01:18,620
So this is the question at hand.

17
00:01:18,740 --> 00:01:21,050
I'm sure we have understood the question.

18
00:01:21,050 --> 00:01:27,410
And remember always before you start solving a coding interview question which is given to you, remember

19
00:01:27,410 --> 00:01:31,100
to ask any clarifying questions that you may want to ask.

20
00:01:31,130 --> 00:01:37,370
A possible question that you may want to ask for this question is, do I need to treat small case and

21
00:01:37,370 --> 00:01:39,530
upper case letters differently?

22
00:01:39,530 --> 00:01:46,490
And let's say the interviewer replies, you will only be given a string that consists of lower case

23
00:01:46,490 --> 00:01:47,240
letters.

24
00:01:47,240 --> 00:01:53,360
So we have understood the question, and we have asked any clarifying questions that we wanted to ask.

25
00:01:53,360 --> 00:01:56,750
Let's now proceed and write a few test cases.

26
00:01:56,750 --> 00:02:02,870
And remember, it's always a good practice to work on this together with the interviewer.

27
00:02:02,870 --> 00:02:08,960
You can come up with test cases along with the interviewer, and this will ensure that both of you are

28
00:02:08,960 --> 00:02:10,040
on the same page.

29
00:02:10,040 --> 00:02:15,470
Now we have a test case which was given to us as an example for the question.

30
00:02:15,470 --> 00:02:19,070
That was the case where a, a, b a was the input string.

31
00:02:19,070 --> 00:02:25,760
And we have seen that these are the three ways of partitioning a, a BA in a way that all the substrings

32
00:02:25,760 --> 00:02:30,350
after we partition the string are palindromes themselves.

33
00:02:30,350 --> 00:02:36,620
Now, if you're given a string with just one character, then the required output would be this.

34
00:02:36,620 --> 00:02:38,960
Again, notice that it's an array of arrays.

35
00:02:38,960 --> 00:02:44,240
And over here again, because there is just one way of partitioning this, we just have one element

36
00:02:44,240 --> 00:02:45,410
in this array.

37
00:02:45,410 --> 00:02:51,500
Another input that we could consider is let's say the array which is given to us is a a.

38
00:02:51,500 --> 00:02:57,170
If this is the input array, the required output would be a a.

39
00:02:57,410 --> 00:02:59,630
So this is one partitioning.

40
00:02:59,780 --> 00:03:03,080
And then you could have a a together right.

41
00:03:04,580 --> 00:03:08,900
So you would have two ways of partitioning the characters over here.

42
00:03:08,900 --> 00:03:12,080
And notice that all of these are palindromes.