1
00:00:00,900 --> 00:00:01,589
Hi, everyone.

2
00:00:01,620 --> 00:00:06,890
So in this video, what we are going to do, we are going to write the deep solution for this problem,

3
00:00:06,900 --> 00:00:08,140
longest common, subsequent.

4
00:00:10,290 --> 00:00:15,830
So what we need to do, we just need to convert this recursive code into our DP are.

5
00:00:16,620 --> 00:00:18,560
So that's going to be very, very simple.

6
00:00:18,570 --> 00:00:22,350
For example, you are with two things, apple and mango.

7
00:00:22,710 --> 00:00:25,740
So what I will do, I will take one string like this.

8
00:00:25,740 --> 00:00:27,250
I will create a Julietta.

9
00:00:29,320 --> 00:00:36,730
I will create one today and I will start from I will start from zero to zero, and then we have Apple.

10
00:00:40,070 --> 00:00:42,750
And similarly, zero, and then we have him go.

11
00:00:44,870 --> 00:00:48,980
So what we are going to do is we will define DPO.

12
00:00:50,180 --> 00:00:56,900
So what Deepthi means so deeply offensive means the longest common subsequence between two strings,

13
00:00:58,010 --> 00:01:00,590
between two strings as to an end as two.

14
00:01:00,920 --> 00:01:03,650
And we are considering i.e. correctors.

15
00:01:04,849 --> 00:01:05,690
For S1.

16
00:01:06,740 --> 00:01:15,370
I characters of Esswein and characters of string, too, right, I'm repeating myself, if I'm not clear

17
00:01:15,650 --> 00:01:18,680
so what the prophecy will contain so deep.

18
00:01:18,680 --> 00:01:27,670
Viji will contain the length, the length of the longest common subsequent four i.e. characters of S1

19
00:01:27,680 --> 00:01:29,440
and the characters of S2.

20
00:01:29,750 --> 00:01:31,790
So in that case, what will answer?

21
00:01:31,970 --> 00:01:34,430
My answer will be DPE of Emelin.

22
00:01:35,790 --> 00:01:43,290
What is so basically this last box, so what is M m is basically the number of characters in the first

23
00:01:43,290 --> 00:01:47,890
string and is the number of characters in the second string sample.

24
00:01:47,940 --> 00:01:48,270
Right.

25
00:01:48,540 --> 00:01:50,830
So it's going to be very, very simple code.

26
00:01:50,850 --> 00:01:53,050
So let's just start writing the code.

27
00:01:55,800 --> 00:01:56,750
So what do you need to do?

28
00:01:56,760 --> 00:01:58,730
First of all, let's comment about this part.

29
00:02:00,300 --> 00:02:02,910
So we need to create one to Ledbury.

30
00:02:04,050 --> 00:02:10,600
So entity and virtual with the size, the answer is and then the array will be of size and plus one

31
00:02:10,620 --> 00:02:12,000
and end plus one.

32
00:02:13,210 --> 00:02:13,680
Right.

33
00:02:15,360 --> 00:02:26,490
And what is Emelin so m is basically let's change the string name here, needs to make it Esswein and

34
00:02:26,490 --> 00:02:27,920
let's make it as two.

35
00:02:29,040 --> 00:02:33,480
So what is missing number of characters present in the first string.

36
00:02:33,480 --> 00:02:34,710
So as our Lord says.

37
00:02:37,750 --> 00:02:43,990
And and there's the number of characters present in this second string, so as to our size and our answer

38
00:02:43,990 --> 00:02:47,800
will be DPF and then so what is the payoff?

39
00:02:47,830 --> 00:02:48,080
And.

40
00:02:49,060 --> 00:02:50,260
So it's very simple.

41
00:02:51,110 --> 00:03:00,130
It is basically the longest the length, the length of the longest common subsequent when we are considering

42
00:03:00,130 --> 00:03:04,570
M characters of string one and end characters of string two.

43
00:03:04,780 --> 00:03:07,270
And that is where the question asked us to do.

44
00:03:07,570 --> 00:03:07,980
Right.

45
00:03:08,260 --> 00:03:11,170
So let's start filling this area.

46
00:03:11,170 --> 00:03:12,110
We will fill this area.

47
00:03:12,400 --> 00:03:16,210
So we'll see if the first string is basically empty.

48
00:03:16,210 --> 00:03:18,240
Then the longest common subsequent will be zero.

49
00:03:18,850 --> 00:03:19,930
So there will be zero.

50
00:03:22,140 --> 00:03:28,980
If my any other string so out of the toasting, if one string is empty, then your output will be zero.

51
00:03:30,190 --> 00:03:30,580
Right.

52
00:03:30,730 --> 00:03:35,110
So if the first thing is empathy, long term subsegments will be zero.

53
00:03:35,110 --> 00:03:38,660
If the second string is empty, your longest common subsequent will be zero.

54
00:03:38,890 --> 00:03:40,040
So that's the best case.

55
00:03:40,060 --> 00:03:41,740
Exactly what you have written here.

56
00:03:41,770 --> 00:03:42,560
Exactly that.

57
00:03:43,390 --> 00:03:45,340
So let's write that.

58
00:03:45,340 --> 00:03:52,720
Let's first do let's first iterate over this area and we will consider this case also.

59
00:03:52,750 --> 00:03:55,390
So I need to fill this area starting from zero.

60
00:03:57,160 --> 00:03:59,410
Am I plus.

61
00:03:59,410 --> 00:03:59,890
Plus.

62
00:04:06,200 --> 00:04:09,860
So here's what I'm going to do is I'm going to fill this, Eddie.

63
00:04:12,350 --> 00:04:19,010
So let's first talk about base case, so base case, it's very simple if any of the string does not

64
00:04:19,010 --> 00:04:19,480
exist.

65
00:04:19,820 --> 00:04:28,580
So if I equals zero or Jaquiss zero, that means if one on the string does not exist, one of them is

66
00:04:28,760 --> 00:04:32,420
predicting either one is assembly or the string, too, is empty.

67
00:04:32,670 --> 00:04:37,910
In that case, the longest common subsequent is going to be zero acres of land.

68
00:04:38,000 --> 00:04:38,450
Zero.

69
00:04:38,450 --> 00:04:39,260
Simple, right?

70
00:04:40,880 --> 00:04:45,960
And after this, for Lluvia going to return you around answer, which will really be off and then as

71
00:04:45,980 --> 00:04:46,580
discussed.

72
00:04:49,430 --> 00:04:51,050
So apart from the base case.

73
00:04:52,680 --> 00:04:58,630
We discussed there will be two cases, match or mismatch, so this is the matching condition, right?

74
00:04:59,370 --> 00:05:01,350
So if we have a match.

75
00:05:03,170 --> 00:05:10,620
Match means, as of eye is Ezequiel's to as two of G.

76
00:05:11,300 --> 00:05:13,060
That means we have a match.

77
00:05:13,910 --> 00:05:28,430
So in case of match our answer will be our answer will be one plus B of A minus one and G minus one.

78
00:05:30,380 --> 00:05:31,250
Simple right.

79
00:05:32,420 --> 00:05:33,890
In case of mismatch.

80
00:05:34,910 --> 00:05:39,490
So in El Spart, if there is a mismatch then DPF.

81
00:05:44,900 --> 00:05:47,210
Then the apology will be the maximum of.

82
00:05:49,280 --> 00:05:54,590
DBF I minus one, Angie.

83
00:05:57,100 --> 00:06:05,620
Plus, both I and G minus one and that.

84
00:06:09,260 --> 00:06:10,550
That's what you need to do.

85
00:06:14,520 --> 00:06:19,530
So let me explain you again, so what I'm doing, I am first finding out this is for both the strings,

86
00:06:19,530 --> 00:06:22,590
then I'm creating this disparity of M plus 100 plus.

87
00:06:22,590 --> 00:06:27,480
And because evidence is going to be the length of the longest common subsequent.

88
00:06:27,510 --> 00:06:32,160
So when we are considering M characters of String one and end characters of string two.

89
00:06:32,640 --> 00:06:33,160
Simple.

90
00:06:33,570 --> 00:06:36,750
So we are iterating over this area, right?

91
00:06:36,780 --> 00:06:43,260
We are all of this debris and while iterating this is our best condition.

92
00:06:44,040 --> 00:06:51,270
So if any of this thing does not exist, then your body will contain zero.

93
00:06:51,270 --> 00:06:54,150
Basically the length of the longest common subsequent will be zero.

94
00:06:54,300 --> 00:06:54,730
Right.

95
00:06:55,770 --> 00:07:02,880
Otherwise, if there is a match, if there is a match, then your answer is going to be one plus I minus

96
00:07:02,880 --> 00:07:03,840
an engine, minus one.

97
00:07:03,990 --> 00:07:04,400
Right.

98
00:07:04,680 --> 00:07:10,410
If there is a match, then your answer will be one plus this value, whatever the value has been stored

99
00:07:10,650 --> 00:07:11,550
in this box.

100
00:07:12,550 --> 00:07:14,370
Otherwise you have two options.

101
00:07:15,530 --> 00:07:20,940
If I am innocent or I and G minus I'm sorry I have written plus here it should be comma.

102
00:07:22,750 --> 00:07:25,240
Right, so let's do that.

103
00:07:29,690 --> 00:07:39,810
So it will be maximum of two things exactly like this, right, exactly like this, maximum of two things.

104
00:07:41,330 --> 00:07:50,540
So here we have done one mistake, and that mistake is basically so that mistake is basically so if

105
00:07:50,540 --> 00:07:59,090
the value of A is M and if the value of G is N, so what they are doing as often as one of em, which

106
00:07:59,090 --> 00:08:05,600
does not exist, the last index is basically Asanov, I mean add because the indexing starts from zero.

107
00:08:05,870 --> 00:08:08,530
So instead of comparing G, what should I do.

108
00:08:08,540 --> 00:08:11,120
I should compare I minus on energy minus one.

109
00:08:11,850 --> 00:08:12,350
Right.

110
00:08:13,010 --> 00:08:14,800
So let's do the correction here.

111
00:08:15,260 --> 00:08:21,200
So it will be a minus one and G minus one.

112
00:08:22,400 --> 00:08:25,640
Now our code is correct and our code will work now.

113
00:08:26,090 --> 00:08:32,210
So let's submit our code and see with our code will work or not.

114
00:08:33,200 --> 00:08:37,320
So let's try to let's try to submit our code.

115
00:08:39,530 --> 00:08:40,049
OK.

116
00:08:40,110 --> 00:08:46,910
So I'm getting runtime errors and so we did some mistake.

117
00:08:46,910 --> 00:08:48,200
What is the mistake?

118
00:08:58,560 --> 00:09:01,330
OK, so I have understood what is the mistake.

119
00:09:01,830 --> 00:09:10,740
So what I'm doing here is, see, I have written if it should be elusive because see if the value of

120
00:09:10,890 --> 00:09:12,080
is zero, what will happen?

121
00:09:12,420 --> 00:09:13,710
I will check this condition.

122
00:09:13,710 --> 00:09:15,690
And what does this condition this condition is?

123
00:09:15,690 --> 00:09:18,750
ASANOV Zero minus, and that is Asanov minus one.

124
00:09:19,270 --> 00:09:22,320
So I should write here instead of writing.

125
00:09:22,320 --> 00:09:26,460
If so, let's correct our code.

126
00:09:27,450 --> 00:09:33,690
So we should write here as if instead of writing if now code is correct.

127
00:09:39,710 --> 00:09:41,580
So our goal is working fine now.

128
00:09:41,600 --> 00:09:43,750
That was a very silly mistake that we have done.

129
00:09:44,150 --> 00:09:47,150
So let's discuss time and space complexity for this problem.

130
00:09:47,420 --> 00:09:50,450
So it's very obvious that the time complexity.

131
00:09:51,380 --> 00:09:58,340
And space complexities, so space complexity is basically you are creating one bit of space and listen

132
00:09:58,610 --> 00:10:01,840
to the space, complexity is basically big of M.

133
00:10:02,760 --> 00:10:10,440
Cross and light, and similarly, what is the time, complexity, so you are trading over your right,

134
00:10:10,680 --> 00:10:13,610
you are trading and then this is basically constant work.

135
00:10:13,620 --> 00:10:17,740
So time, complexities and then multiply.

136
00:10:17,770 --> 00:10:22,410
And so this is the time and the space complexity for this problem.

137
00:10:24,060 --> 00:10:24,460
Right.

138
00:10:24,750 --> 00:10:27,130
So that is all that I want to discuss in this video.

139
00:10:27,750 --> 00:10:28,860
So this is it, guys.

140
00:10:29,040 --> 00:10:30,610
I will see you in the next one.

141
00:10:31,020 --> 00:10:31,560
Thank you.