1
00:00:00,440 --> 00:00:01,490
Welcome back.

2
00:00:01,490 --> 00:00:07,700
Let's now get started with another interesting coding interview question, which is called Palindrome

3
00:00:07,700 --> 00:00:08,810
Partitioning two.

4
00:00:09,290 --> 00:00:18,110
The question reads given a string s partition s such that every substring of the partition is a palindrome,

5
00:00:18,350 --> 00:00:21,980
return the minimum cuts needed for a palindrome.

6
00:00:21,980 --> 00:00:27,260
Partitioning of S s will not be an empty string, and we are given an example.

7
00:00:27,260 --> 00:00:29,990
Let's say the string given to us is a b, b.

8
00:00:30,020 --> 00:00:36,620
Now the output required is equal to one, because the minimum number of cuts required to partition this

9
00:00:36,620 --> 00:00:42,650
into sub strings in a manner that every substring is a palindrome is equal to one, which is this cut

10
00:00:42,650 --> 00:00:43,280
over here.

11
00:00:43,280 --> 00:00:45,860
Remember, you could do it also in this manner.

12
00:00:45,860 --> 00:00:48,800
Like you could have a cut over here and a cut over here.

13
00:00:48,800 --> 00:00:51,800
But then in this case you would need two cuts.

14
00:00:51,800 --> 00:00:56,000
But we are asked to identify the minimum cuts required which is equal to one.

15
00:00:56,210 --> 00:00:59,750
Now the question is pretty straightforward to understand.

16
00:00:59,750 --> 00:01:05,600
And do remember to ask any clarifying questions you may want to ask when you are presented with a coding

17
00:01:05,600 --> 00:01:06,470
interview question.

18
00:01:06,830 --> 00:01:12,290
Now, a possible question that you could ask over here is do I need to treat uppercase and lowercase

19
00:01:12,290 --> 00:01:13,700
letters differently?

20
00:01:13,700 --> 00:01:20,240
And let's say the interviewer replies that you will only be given a string that consists of lowercase

21
00:01:20,240 --> 00:01:21,140
characters.

22
00:01:21,470 --> 00:01:25,940
So we have understood the question and we have asked any clarifying questions that we had.

23
00:01:25,940 --> 00:01:28,760
Now let's proceed and write a few test cases.

24
00:01:29,120 --> 00:01:32,810
Now we already were given an example.

25
00:01:32,810 --> 00:01:40,160
If the input is AB, then the output expected is one, because you can partition this into sub strings

26
00:01:40,160 --> 00:01:44,120
where every substring is a palindrome with just one cut over here.

27
00:01:44,150 --> 00:01:51,140
Now, if the string which is given to you is just a or if it has just one character, then this itself

28
00:01:51,140 --> 00:01:54,530
is a palindrome and therefore we do not need any cuts.

29
00:01:54,530 --> 00:01:59,060
And if the string which is given to us is b a, we would need one cut.

30
00:01:59,450 --> 00:02:06,620
Another test case is if the string is ab a, then we would not require any cut because ab a is a palindrome,

31
00:02:06,620 --> 00:02:10,280
and if the string which is given to us is ab a CD.

32
00:02:10,340 --> 00:02:14,030
Notice that you would need two cuts because this is a palindrome.

33
00:02:14,030 --> 00:02:15,740
And then we have these two over here.

34
00:02:15,740 --> 00:02:19,040
So the total number of cuts required is equal to two.

35
00:02:19,070 --> 00:02:25,130
Now remember writing test cases is a very important step because it helps you think deeply about the

36
00:02:25,130 --> 00:02:26,000
problem at hand.