1
00:00:00,450 --> 00:00:02,520
Hi, everyone, welcome to this new video.

2
00:00:02,550 --> 00:00:08,820
So in this video, we are going to solve one question and find out the longest common subsequence between

3
00:00:08,820 --> 00:00:09,590
two strings.

4
00:00:10,110 --> 00:00:13,820
So first of all, let us try to understand, what do we mean by a subsequence?

5
00:00:14,580 --> 00:00:20,550
So far, this string, the subsequence can be Eppy.

6
00:00:20,790 --> 00:00:22,170
It can be easily.

7
00:00:22,650 --> 00:00:30,510
It can be E, it can be B. It can be B, B and so on.

8
00:00:30,600 --> 00:00:33,810
So now we know what is the meaning of subsequence.

9
00:00:34,440 --> 00:00:40,650
So given to string, first string and the second string, we need to find out the longest common subsequent

10
00:00:40,650 --> 00:00:41,280
between them.

11
00:00:41,490 --> 00:00:48,950
So in this case, the longest common subsequence will be E and the length is one rate.

12
00:00:49,140 --> 00:00:51,810
So E is present here is also present.

13
00:00:51,810 --> 00:00:56,550
Here is the longest common subsequent and the length is one.

14
00:00:56,550 --> 00:00:58,440
So we need to return the land.

15
00:00:58,770 --> 00:01:02,520
We need to return the length of the longest common subsequent.

16
00:01:03,160 --> 00:01:04,739
Let's talk about this example.

17
00:01:05,610 --> 00:01:11,340
So we have a we have it then we have this B soapies here then.

18
00:01:11,340 --> 00:01:12,860
And so Elly's here.

19
00:01:13,140 --> 00:01:19,680
So in this case, the longest common subsequence is basically A, B, L and E.

20
00:01:20,610 --> 00:01:22,650
So my answer will be for.

21
00:01:23,740 --> 00:01:31,030
Right, so a U.S. president here is present here, B.L. is present here and police present here.

22
00:01:31,040 --> 00:01:36,160
So that's why Epperly is the longest common subsequence of land for.

23
00:01:36,520 --> 00:01:40,360
So our answer will be land for now.

24
00:01:40,360 --> 00:01:42,340
Let's talk about third example.

25
00:01:44,320 --> 00:01:56,020
Apple and this word, this random world, so we have a we have A we have E, so we have it here and

26
00:01:56,020 --> 00:02:06,400
yes, so in this case, the longest common subsequent is basically E and E, so e e and this is A.

27
00:02:06,730 --> 00:02:08,419
So the length is basically two.

28
00:02:08,440 --> 00:02:13,580
So in this case, my answer should be to the length of the longest common subsequent is basically two.

29
00:02:13,840 --> 00:02:16,070
So I hope you have understood the problem statement.

30
00:02:16,300 --> 00:02:21,340
So how we can solve this question so we can easily solve this question with the help of recursion,

31
00:02:22,960 --> 00:02:24,320
how the will help us.

32
00:02:24,640 --> 00:02:26,580
So let's consider two strings.

33
00:02:27,160 --> 00:02:34,330
So this is my first string apple and this is my second string mple.

34
00:02:35,430 --> 00:02:35,820
Right.

35
00:02:36,120 --> 00:02:37,000
So what I will do.

36
00:02:37,500 --> 00:02:39,960
Let's take one variable I here.

37
00:02:42,540 --> 00:02:51,240
Let me reiterate again, so I have this string apple and I have an added string, which is Apple, so

38
00:02:51,240 --> 00:02:58,780
take two indexes index xiphoid rating in order for a string index for our trading over the second string.

39
00:02:59,100 --> 00:03:01,830
Now, I ended the article.

40
00:03:03,340 --> 00:03:09,800
So this match there is match, match means I got equals.

41
00:03:09,810 --> 00:03:17,170
So if I and the guy recall what we do, we will tell Dacogen, find out the answer for this part and

42
00:03:17,350 --> 00:03:18,030
this part.

43
00:03:18,430 --> 00:03:24,580
So my answer will be, I have one I have one common character between these two.

44
00:03:25,120 --> 00:03:33,150
Samantha will be one plus the longest common subsequent between this string and this string.

45
00:03:33,490 --> 00:03:36,160
So I will call the function longest common subsequence.

46
00:03:36,970 --> 00:03:44,860
Let's say this is string one, this is string to string one, and the rest of the string of the string

47
00:03:44,860 --> 00:03:45,830
is a plus one.

48
00:03:46,120 --> 00:03:55,390
Similarly, string two and rest of this string find out the longest common subsequent between the rest

49
00:03:55,390 --> 00:03:55,980
of the string.

50
00:03:55,990 --> 00:04:04,350
So J plus one, if there is a match, then in that case this will be my answer.

51
00:04:05,560 --> 00:04:05,940
Fine.

52
00:04:06,340 --> 00:04:09,340
So what this function will do, this is a recursive function.

53
00:04:09,580 --> 00:04:14,650
This takes two string as input and it gives us the longest common subsequent Slint.

54
00:04:15,490 --> 00:04:15,930
Right.

55
00:04:16,750 --> 00:04:23,770
So what I'm doing here is if the character matches, if there is a match, if there's a match, then

56
00:04:24,580 --> 00:04:30,580
the answer will be one because there is a match then and case of rest of the string.

57
00:04:30,910 --> 00:04:33,880
Similarly altius of the rest of the string.

58
00:04:34,300 --> 00:04:36,630
Now if there is no match.

59
00:04:37,780 --> 00:04:42,280
So if we do not have a match in case of mismatch.

60
00:04:42,970 --> 00:04:45,490
So let's take one example here.

61
00:04:46,540 --> 00:04:55,740
If I have this, let's say this is one string and we have another string, let's say this one.

62
00:04:57,460 --> 00:04:58,870
So we have these two string.

63
00:04:59,680 --> 00:05:02,140
I is here, G is here.

64
00:05:02,140 --> 00:05:03,640
This is string one.

65
00:05:04,090 --> 00:05:05,510
This is string two.

66
00:05:05,890 --> 00:05:11,170
Now if we will compare so string I is not close to string.

67
00:05:11,170 --> 00:05:17,530
So the correct that I is not close to character G so this is the case for mismatch.

68
00:05:18,250 --> 00:05:18,730
Right.

69
00:05:18,910 --> 00:05:20,340
So we have a mismatch here.

70
00:05:20,560 --> 00:05:23,020
So in mismatch we have two possibilities.

71
00:05:24,940 --> 00:05:26,080
We have two possibilities.

72
00:05:26,110 --> 00:05:27,940
First is I will tell recursion.

73
00:05:28,860 --> 00:05:30,740
To find out the answer for.

74
00:05:32,160 --> 00:05:35,880
To find out the longest common subsequent between the m'appelle and.

75
00:05:37,740 --> 00:05:46,830
M'appelle and the second possibility is find out the subsequence between Apple and Apple and repeating

76
00:05:46,830 --> 00:05:52,440
myself, I'm going to compare AMG so Iyengar different.

77
00:05:52,590 --> 00:05:53,790
That is mismatch.

78
00:05:55,150 --> 00:05:58,270
So in case of mismatch, I have two options.

79
00:05:59,190 --> 00:06:06,630
So the first option is basically I will tell the commission to find out the answer for this string.

80
00:06:08,520 --> 00:06:10,110
And this is string.

81
00:06:12,610 --> 00:06:21,190
So that's why m'appelle the entire string and this reduced string emboli, so in this case, what I'm

82
00:06:21,190 --> 00:06:28,690
doing, Stringbean and I will not string two and G plus one, we need to pass the rest of the string.

83
00:06:28,690 --> 00:06:32,250
So J.s here, we need to pass that statistics of J plus one.

84
00:06:32,530 --> 00:06:35,850
The second option is what we will do.

85
00:06:36,100 --> 00:06:46,030
So second option is take this entire string, take this entire string and reduce this string.

86
00:06:48,790 --> 00:06:54,580
So reducing the strength will become a both and we will take this interesting, so this is ample.

87
00:06:54,620 --> 00:07:00,920
So in this case it will be one and the string and the string two will remain the same.

88
00:07:02,590 --> 00:07:09,910
So it is useful to tell me the length of the longest common subsequent similarly for this also and will

89
00:07:09,910 --> 00:07:12,060
determine the length of longest subsequence.

90
00:07:12,360 --> 00:07:13,800
So in this case, where to leave?

91
00:07:13,830 --> 00:07:18,490
My answer, my answer will be zero plus zero because there is a mismatch, right?

92
00:07:19,060 --> 00:07:20,880
Zero because we have a mismatch here.

93
00:07:20,890 --> 00:07:24,990
Zero plus I have two options, so I will take the some of them.

94
00:07:25,450 --> 00:07:26,620
So I have two options.

95
00:07:26,840 --> 00:07:28,920
Let's say this is first option.

96
00:07:29,050 --> 00:07:30,400
This is second option.

97
00:07:30,700 --> 00:07:35,860
So the maximum of option one and option two, that will be my answer.

98
00:07:37,130 --> 00:07:37,970
Simple, right.

99
00:07:38,920 --> 00:07:45,970
So I discussed both the cases in case of match the this is our recursive formula in case of mismatch.

100
00:07:46,000 --> 00:07:47,720
This is our recursive formula.

101
00:07:49,150 --> 00:07:56,610
So this question is basically present on netcode, longest common subsequent.

102
00:07:56,650 --> 00:08:02,240
So what we are going to do is let us first write the recursive approach for solving this problem.

103
00:08:02,680 --> 00:08:04,690
So let's start writing the code.

104
00:08:08,580 --> 00:08:15,930
So we have a function, the function will return the longest common subsequent, so let's say the name

105
00:08:15,930 --> 00:08:18,780
of the function is is what it takes.

106
00:08:19,950 --> 00:08:22,140
It takes two strings, right?

107
00:08:22,590 --> 00:08:24,540
So string S1.

108
00:08:26,020 --> 00:08:34,419
And its index similarly string as to and its index.

109
00:08:37,510 --> 00:08:41,530
First of all, we need to discuss about the base case, so this case is very simple.

110
00:08:42,760 --> 00:08:46,660
If I is basically Esswein darte size.

111
00:08:50,330 --> 00:09:01,340
Or, gee, is it close to a the size then in that case, what will be the longest common subsequent?

112
00:09:01,340 --> 00:09:02,070
It will be zero.

113
00:09:04,630 --> 00:09:13,330
So if string one does not exist or string two does not exist, then in that case, if one of the string

114
00:09:13,330 --> 00:09:15,420
does not exist, then your answer will be zero.

115
00:09:15,460 --> 00:09:16,660
You cannot find longer term.

116
00:09:16,660 --> 00:09:22,810
And subsequently, if one of the string does not exist simple right now, what are you to do?

117
00:09:24,590 --> 00:09:31,010
You need to check whether there is a match or mismatch, so let's check in case of match.

118
00:09:31,370 --> 00:09:38,900
So that is as of I will be equal to as two of you.

119
00:09:40,040 --> 00:09:43,360
So, yes, there is a match in case of match.

120
00:09:43,370 --> 00:09:44,340
What is our answer?

121
00:09:44,690 --> 00:09:49,480
Our answer is one plus and is off.

122
00:09:49,910 --> 00:09:52,940
We will pass since is a match.

123
00:09:52,970 --> 00:09:57,320
So when plus we need to pass the rest of the string.

124
00:09:57,320 --> 00:10:04,040
So rest of the string is Esswein and IHI plus one as two and G plus one.

125
00:10:05,420 --> 00:10:05,870
Simple.

126
00:10:05,870 --> 00:10:06,260
Right.

127
00:10:06,620 --> 00:10:08,490
And in case of mismatch.

128
00:10:08,630 --> 00:10:12,170
So in case of mismatch.

129
00:10:12,240 --> 00:10:19,010
So this is the case for match in case there is a match and this is the case for mismatch.

130
00:10:19,010 --> 00:10:27,140
So in mismatch, what we're gonna do is we will, our answer will be zero plus or let's not write zero

131
00:10:27,410 --> 00:10:27,830
plus.

132
00:10:27,830 --> 00:10:29,890
Let's simply write Alex off.

133
00:10:29,900 --> 00:10:31,820
I have two options here, right?

134
00:10:32,150 --> 00:10:33,080
I have two options.

135
00:10:33,080 --> 00:10:37,600
The first option is S1 and I and J.

136
00:10:37,640 --> 00:10:38,210
Plus one.

137
00:10:40,720 --> 00:10:46,870
Second option was Altius off S1.

138
00:10:48,250 --> 00:10:57,850
I plus one, and as to gee, these are the two options that we have and we need to find out the longest

139
00:10:57,850 --> 00:10:58,960
common subsequent right.

140
00:10:58,970 --> 00:11:00,190
We need to find our longest.

141
00:11:00,460 --> 00:11:01,960
So we'll take the mix of them.

142
00:11:03,380 --> 00:11:10,070
So we'll take the maximum of two possible options, myxoma first and second option, that will be our

143
00:11:10,070 --> 00:11:10,520
answer.

144
00:11:12,910 --> 00:11:13,370
Right.

145
00:11:13,900 --> 00:11:19,100
So, yeah, that's the complete code and let us call this function string.

146
00:11:20,020 --> 00:11:21,580
So I did it on Altius.

147
00:11:22,300 --> 00:11:31,150
It takes string one, which is one I will start from zero, obviously, string two, which is text two,

148
00:11:31,720 --> 00:11:33,960
and I will start from zero obviously.

149
00:11:35,470 --> 00:11:38,650
So yeah let's FirstRand our code and then we will submit.

150
00:11:44,860 --> 00:11:48,160
So, yeah, our solution is working fine now, something called.

151
00:11:53,280 --> 00:11:59,010
So basically, we are getting timely redecorated, and it's obvious because this is recursive solution,

152
00:11:59,010 --> 00:11:59,370
right?

153
00:12:00,330 --> 00:12:01,770
This is recursive solution.

154
00:12:02,520 --> 00:12:03,810
Our solution is correct.

155
00:12:03,810 --> 00:12:07,260
Our solution will give the right output.

156
00:12:07,410 --> 00:12:09,080
But this is a recursive.

157
00:12:09,090 --> 00:12:11,220
So that's why we are getting timely and excited.

158
00:12:11,760 --> 00:12:13,700
So what do we do in NextRadio?

159
00:12:13,710 --> 00:12:16,710
We will write the dynamic programming code for this problem.

160
00:12:17,190 --> 00:12:20,490
So if you want, you can try writing the code yourself.

161
00:12:20,500 --> 00:12:22,230
Otherwise you can watch the next redo.

162
00:12:22,230 --> 00:12:29,010
And in the next video we will convert this recursive approach into dynamic programming code so that

163
00:12:29,220 --> 00:12:30,270
from this device.

164
00:12:30,480 --> 00:12:31,930
I will see you in the next one.

165
00:12:31,950 --> 00:12:32,490
Thank you.

