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.