Hey there and welcome back.
So far, whenever we implemented tabulation solutions, we had a DP table and we would iterate row wise.
Now in this video let me introduce you to a different strategy which is the gap strategy or lengthwise
iteration.
Now in this case for this method we would have a DP table like this.
And then we would iterate diagonally.
So you can see that first these cells would be covered in the first iteration.
And in the next iteration we will cover these cells.
And then it would go on in a similar manner.
So over here we are going diagonally.
And this is what we call the gap strategy.
Now it's called gap strategy or lengthwise iteration for a reason.
Now again let me write the indices over here.
We have 0123 and four and 0123.
And four.
Now we will soon see questions where this is very useful.
But over here I'm just getting you introduced to this method.
So let's say that we have the same string of length five placed over here which is represented by the
columns.
So let's say the string is a, b, c, d, e.
And let's say we have the same string over here as well.
So we have a b c d e.
Now notice that this cell over here represents the combination zero zero.
And over here we have one one.
Over here we have two two.
We have three three over here and four four over here.
Now the length of these individual substrings is equal to one.
But this cell over here represents the substring going from zero up to one which is of length two.
And over here this substring goes from 1 to 2 which is this substring bc.
Again notice it has the length two.
So every substring over here in this diagonal has a length equal to one, and every substring in this
diagonal has length equal to two.
And over here the substrings would have length equal to three.
Over here we have length equal to four.
And this substring has length equal to five.
So that's why we call this length wise iteration.
And let's also take a look at why we call this gap strategy.
Notice that the gap between these two pointers keeps increasing.
For example over here notice that the gap is equal to zero or this cell is zero zero.
This is one one.
This is two two.
This is three three.
This is four four.
So for this diagonal gap is equal to zero or the gap between two pointers let's say four rows.
We are using the pointer I.
And for columns we are using the pointer j.
So the difference between these two or the gap is equal to zero for this diagonal.
But over here I zero and j is one.
Over here I is one, j is two.
So notice that the gap between I and j for this diagonal is equal to one.
So over here for this diagonal the gap would be equal to two.
And for this diagonal the gap would be equal to three.
And for this cell over here the gap would be equal to four.
So notice that the gap is also increasing from zero up to four.
And that's why this method can also be called the gap strategy.
Now we will soon see a variety of problems which can be easily solved using the gap strategy or using
lengthwise iteration.
And after this section, we will also take a look at the partition method, which is another technique
for solving DP questions.
And the partition method is actually built on top of the lengthwise iteration or gap strategy method.
So let's get started with a few interesting coding interview questions that can be solved using this
methodology.