1
00:00:00,550 --> 00:00:02,440
Hey there and welcome back.

2
00:00:02,440 --> 00:00:11,470
So far, whenever we implemented tabulation solutions, we had a DP table and we would iterate row wise.

3
00:00:12,070 --> 00:00:20,320
Now in this video let me introduce you to a different strategy which is the gap strategy or lengthwise

4
00:00:20,320 --> 00:00:21,160
iteration.

5
00:00:21,190 --> 00:00:26,530
Now in this case for this method we would have a DP table like this.

6
00:00:26,530 --> 00:00:28,990
And then we would iterate diagonally.

7
00:00:28,990 --> 00:00:33,580
So you can see that first these cells would be covered in the first iteration.

8
00:00:33,580 --> 00:00:37,270
And in the next iteration we will cover these cells.

9
00:00:37,270 --> 00:00:40,180
And then it would go on in a similar manner.

10
00:00:40,180 --> 00:00:42,610
So over here we are going diagonally.

11
00:00:42,610 --> 00:00:45,610
And this is what we call the gap strategy.

12
00:00:45,610 --> 00:00:51,190
Now it's called gap strategy or lengthwise iteration for a reason.

13
00:00:51,190 --> 00:00:53,440
Now again let me write the indices over here.

14
00:00:53,440 --> 00:00:59,620
We have 0123 and four and 0123.

15
00:00:59,620 --> 00:01:00,580
And four.

16
00:01:00,580 --> 00:01:04,570
Now we will soon see questions where this is very useful.

17
00:01:04,570 --> 00:01:08,230
But over here I'm just getting you introduced to this method.

18
00:01:08,230 --> 00:01:15,970
So let's say that we have the same string of length five placed over here which is represented by the

19
00:01:15,970 --> 00:01:16,540
columns.

20
00:01:16,540 --> 00:01:19,330
So let's say the string is a, b, c, d, e.

21
00:01:19,540 --> 00:01:22,540
And let's say we have the same string over here as well.

22
00:01:22,540 --> 00:01:25,540
So we have a b c d e.

23
00:01:25,780 --> 00:01:31,390
Now notice that this cell over here represents the combination zero zero.

24
00:01:31,390 --> 00:01:32,860
And over here we have one one.

25
00:01:32,860 --> 00:01:34,150
Over here we have two two.

26
00:01:34,180 --> 00:01:36,940
We have three three over here and four four over here.

27
00:01:36,940 --> 00:01:42,490
Now the length of these individual substrings is equal to one.

28
00:01:42,490 --> 00:01:49,450
But this cell over here represents the substring going from zero up to one which is of length two.

29
00:01:49,450 --> 00:01:55,600
And over here this substring goes from 1 to 2 which is this substring bc.

30
00:01:55,630 --> 00:01:57,970
Again notice it has the length two.

31
00:01:58,000 --> 00:02:05,410
So every substring over here in this diagonal has a length equal to one, and every substring in this

32
00:02:05,410 --> 00:02:08,440
diagonal has length equal to two.

33
00:02:08,440 --> 00:02:12,310
And over here the substrings would have length equal to three.

34
00:02:12,490 --> 00:02:14,350
Over here we have length equal to four.

35
00:02:14,710 --> 00:02:17,620
And this substring has length equal to five.

36
00:02:17,620 --> 00:02:20,860
So that's why we call this length wise iteration.

37
00:02:20,860 --> 00:02:24,820
And let's also take a look at why we call this gap strategy.

38
00:02:24,850 --> 00:02:29,470
Notice that the gap between these two pointers keeps increasing.

39
00:02:29,590 --> 00:02:35,620
For example over here notice that the gap is equal to zero or this cell is zero zero.

40
00:02:35,650 --> 00:02:37,030
This is one one.

41
00:02:37,030 --> 00:02:37,840
This is two two.

42
00:02:37,870 --> 00:02:38,830
This is three three.

43
00:02:38,830 --> 00:02:40,270
This is four four.

44
00:02:40,270 --> 00:02:48,040
So for this diagonal gap is equal to zero or the gap between two pointers let's say four rows.

45
00:02:48,040 --> 00:02:49,600
We are using the pointer I.

46
00:02:49,600 --> 00:02:52,180
And for columns we are using the pointer j.

47
00:02:52,180 --> 00:02:57,220
So the difference between these two or the gap is equal to zero for this diagonal.

48
00:02:57,220 --> 00:03:00,010
But over here I zero and j is one.

49
00:03:00,010 --> 00:03:01,840
Over here I is one, j is two.

50
00:03:01,840 --> 00:03:06,640
So notice that the gap between I and j for this diagonal is equal to one.

51
00:03:06,640 --> 00:03:10,210
So over here for this diagonal the gap would be equal to two.

52
00:03:10,210 --> 00:03:13,030
And for this diagonal the gap would be equal to three.

53
00:03:13,030 --> 00:03:16,480
And for this cell over here the gap would be equal to four.

54
00:03:16,480 --> 00:03:20,890
So notice that the gap is also increasing from zero up to four.

55
00:03:20,890 --> 00:03:24,880
And that's why this method can also be called the gap strategy.

56
00:03:24,880 --> 00:03:32,200
Now we will soon see a variety of problems which can be easily solved using the gap strategy or using

57
00:03:32,200 --> 00:03:33,550
lengthwise iteration.

58
00:03:33,550 --> 00:03:40,090
And after this section, we will also take a look at the partition method, which is another technique

59
00:03:40,090 --> 00:03:41,980
for solving DP questions.

60
00:03:41,980 --> 00:03:49,300
And the partition method is actually built on top of the lengthwise iteration or gap strategy method.

61
00:03:49,300 --> 00:03:56,050
So let's get started with a few interesting coding interview questions that can be solved using this

62
00:03:56,050 --> 00:03:56,980
methodology.