1 00:00:02,410 --> 00:00:03,110 Hi, everyone. 2 00:00:03,130 --> 00:00:08,300 So in this video, we are going to solve this question, find the longest common prefix. 3 00:00:08,710 --> 00:00:10,020 So what will be the input? 4 00:00:10,240 --> 00:00:13,810 So input is basically a vector string, OK? 5 00:00:13,870 --> 00:00:15,600 Input is basically a very trusting. 6 00:00:15,790 --> 00:00:21,190 And what we have to do, we have to find the longest common prefix among all the strings. 7 00:00:21,460 --> 00:00:22,670 Let us take some example. 8 00:00:22,900 --> 00:00:24,610 So these are many strings. 9 00:00:24,610 --> 00:00:29,120 String one string doing a string three, we have to find common prefix. 10 00:00:29,650 --> 00:00:31,610 So in this case, what is the common prefix? 11 00:00:31,690 --> 00:00:34,330 So this is the common flix, common prefix. 12 00:00:35,350 --> 00:00:38,430 So my output in this case is basically string A. 13 00:00:39,590 --> 00:00:41,760 OK, let us consider this example. 14 00:00:42,230 --> 00:00:45,500 So in this example, what is the longest common prefix? 15 00:00:45,590 --> 00:00:46,700 So if Al. 16 00:00:48,620 --> 00:00:53,380 So F.L. is basically the longest common prefix, so my output will be F.L.. 17 00:00:55,790 --> 00:00:59,860 Let us consider this case so the string one string to end a string three. 18 00:01:00,050 --> 00:01:02,670 So in this case, we do not have any common prefix. 19 00:01:02,670 --> 00:01:05,000 So my output will be basically empty string. 20 00:01:05,450 --> 00:01:07,550 My output will be basically empty string. 21 00:01:08,240 --> 00:01:10,250 Now, in this case, what would be my answer? 22 00:01:10,520 --> 00:01:12,260 So this will be my answer. 23 00:01:14,130 --> 00:01:15,120 OK, durably. 24 00:01:16,580 --> 00:01:24,540 So my output in this case is basically the common prefix is basically GW, so this is very simple problem. 25 00:01:24,830 --> 00:01:27,410 So this is basically an implementation problem. 26 00:01:28,450 --> 00:01:33,400 OK, so what we will do, but we'll also consider this example, so what I will do, I will pick the 27 00:01:33,400 --> 00:01:34,250 first character. 28 00:01:35,350 --> 00:01:38,350 So the first character is, gee, now what will do? 29 00:01:38,350 --> 00:01:43,500 I will iterate over all the string and I will check g g g. 30 00:01:43,810 --> 00:01:44,520 It is fine. 31 00:01:44,520 --> 00:01:45,380 Now go for it. 32 00:01:45,610 --> 00:01:48,010 OK, so e what do you do after finding out. 33 00:01:48,010 --> 00:01:48,760 Geez, fine. 34 00:01:49,210 --> 00:01:55,150 Let's say this is your answer string you will appended to your answer string now e so e present everywhere. 35 00:01:56,230 --> 00:01:58,240 Pick the title character e so easy. 36 00:01:58,240 --> 00:02:00,580 Also present in all the in all of the string. 37 00:02:00,580 --> 00:02:04,720 So you will spend any at all times for this one and for this one. 38 00:02:05,020 --> 00:02:05,880 Now here it is. 39 00:02:06,380 --> 00:02:14,980 So OK, but here I have said OK, so since there is a difference what I will do, I will stop at this 40 00:02:14,980 --> 00:02:15,400 point. 41 00:02:15,820 --> 00:02:19,210 What I will do, I will stop and this will be my answer. 42 00:02:19,540 --> 00:02:24,940 GWC OK, so what we are doing, we are doing character by character matching, ok. 43 00:02:26,480 --> 00:02:32,480 We are doing character by connecting, writing, character matching, this is simply implementation 44 00:02:32,480 --> 00:02:37,570 problem, make the first character now check whether that character is present in all of this string 45 00:02:37,580 --> 00:02:38,000 or not. 46 00:02:38,330 --> 00:02:42,170 Now, the second character, if it is present in all of the string Apprendi, would answer. 47 00:02:43,830 --> 00:02:49,380 Check for the third category of the title character is also present in all the strings, then a bandos 48 00:02:49,380 --> 00:02:50,340 correct in your answer. 49 00:02:50,460 --> 00:02:55,560 Similarly, the fourth character, the fourth character is not listing at this point. 50 00:02:55,860 --> 00:03:01,140 As soon as you find a character that is not present in all of the string, you will stop and you will 51 00:03:01,140 --> 00:03:02,070 return your answer. 52 00:03:02,370 --> 00:03:05,400 And initially your answer will basically be empty string. 53 00:03:06,460 --> 00:03:09,140 Very simple, simple implementation problem. 54 00:03:09,700 --> 00:03:15,450 Now we can write the code, so this basically is a little problem, longest common prefix. 55 00:03:15,540 --> 00:03:18,700 We have to return the string, we have to return the longest common string. 56 00:03:18,730 --> 00:03:21,440 OK, and we are giving crusting as input. 57 00:03:21,460 --> 00:03:22,660 The name is strings. 58 00:03:23,930 --> 00:03:29,550 OK, now let us write the code, so string answer, which is basically initially empty. 59 00:03:29,630 --> 00:03:31,580 OK, this is AMP listing initially. 60 00:03:32,390 --> 00:03:35,540 Now, let us first try to find out the minimum string. 61 00:03:35,690 --> 00:03:38,300 OK, so our function, main element. 62 00:03:39,800 --> 00:03:44,960 So main element will take the beginning of the vector and the end of the vector, so the name of that 63 00:03:44,960 --> 00:03:46,430 is start with strings. 64 00:03:46,430 --> 00:03:49,400 So it will take the beginning and at the end. 65 00:03:49,430 --> 00:03:49,790 OK. 66 00:03:52,950 --> 00:03:59,880 So this minimum element, what it will return, so this will return me, this will return me the minimum 67 00:03:59,880 --> 00:04:06,810 string, OK, meaning testing means basically the string which has the lowest length, OK, lowest size, 68 00:04:07,590 --> 00:04:08,420 minimum size. 69 00:04:08,430 --> 00:04:10,320 So it will it'll be the minimum size of string. 70 00:04:10,650 --> 00:04:11,580 Now what we have to do. 71 00:04:12,610 --> 00:04:20,110 So this example so in this example, what is the medium size of string, so this is geek geeky, OK, 72 00:04:20,620 --> 00:04:23,740 let's call it s so system in size and string. 73 00:04:23,740 --> 00:04:25,480 It is G EKI. 74 00:04:26,520 --> 00:04:30,930 Now, what I will do, I will iterate over this string, I will add it over the string, what they will 75 00:04:30,930 --> 00:04:31,060 do. 76 00:04:31,080 --> 00:04:37,920 I will pick the first character now after picking the first character I read or this Vector and Quddus, 77 00:04:37,940 --> 00:04:43,240 president, president, president, president, president Dan Apprendi here. 78 00:04:43,310 --> 00:04:44,130 OK, Benji. 79 00:04:44,370 --> 00:04:48,120 Now pick the second character E so is present everywhere. 80 00:04:49,430 --> 00:04:58,600 Support E now e so check is present in all the strings, so put E now, so check is not present in all 81 00:04:58,610 --> 00:04:59,010 listing. 82 00:04:59,060 --> 00:04:59,890 This is not present. 83 00:04:59,900 --> 00:05:04,150 So at this point you will stop and you will return on Salvages GW. 84 00:05:04,580 --> 00:05:06,470 OK, simple one. 85 00:05:07,190 --> 00:05:12,050 What we are doing first, this is, this will be Mallalieu Biomet rating over this more or less a string. 86 00:05:12,470 --> 00:05:16,220 Then I'm picking each and every character and Armatrading over this. 87 00:05:16,970 --> 00:05:17,970 All of the strings. 88 00:05:17,990 --> 00:05:18,950 OK, simple one. 89 00:05:21,310 --> 00:05:22,210 Now, what we have to do. 90 00:05:23,710 --> 00:05:31,630 We have to iterate over this string as, OK, the minimum string, so in order to set it so in DayQuil 91 00:05:31,640 --> 00:05:34,300 zero, Ellerston Astarte size. 92 00:05:36,510 --> 00:05:42,900 OK, I am editing out the smallest string now, I am picking the first character, I will pick all the 93 00:05:42,920 --> 00:05:47,160 characters of the string and now I will get rid over this strings. 94 00:05:47,160 --> 00:05:49,410 OK, OK, I will get right over these strings. 95 00:05:49,410 --> 00:05:55,470 So, Jake, zero g listin strings, dot size. 96 00:05:56,780 --> 00:05:58,550 And duplicitous, what do you have to do? 97 00:05:58,880 --> 00:06:00,270 I will compared the character. 98 00:06:00,330 --> 00:06:00,680 OK. 99 00:06:01,710 --> 00:06:04,740 So I will compare the character of the smallest string. 100 00:06:05,780 --> 00:06:12,470 With the Ayyad character, with the character of the Geth string, if they are not equal, that means. 101 00:06:13,690 --> 00:06:17,780 There is no more common prefix and you can anywhere and said, OK. 102 00:06:19,220 --> 00:06:22,250 Now, if the character is present in all resting. 103 00:06:23,490 --> 00:06:26,490 You will apprehend the current Indian substring. 104 00:06:26,520 --> 00:06:28,020 OK, so I said I'd push back. 105 00:06:29,090 --> 00:06:29,960 I character. 106 00:06:31,630 --> 00:06:37,240 Simple and finally, you can read an answer here also, OK, don't answer. 107 00:06:37,630 --> 00:06:39,820 So this is the complete code, OK? 108 00:06:40,180 --> 00:06:41,260 This is the complete cold. 109 00:06:41,650 --> 00:06:42,880 Let us take an example. 110 00:06:43,990 --> 00:06:47,260 So in this case, I am finding out the minimum element. 111 00:06:47,290 --> 00:06:48,610 So what is the minimum element? 112 00:06:48,610 --> 00:06:49,810 Fluid's the minimum element. 113 00:06:49,840 --> 00:06:55,240 OK, so FLW, this is the minimum element and that's what the strings are, basically flower. 114 00:06:56,250 --> 00:06:57,060 And flight. 115 00:06:59,820 --> 00:07:02,760 So what I'm doing, I'm iterating over this floor. 116 00:07:03,600 --> 00:07:04,620 OK, pick the first. 117 00:07:04,820 --> 00:07:06,680 But if no check if it's pleasant. 118 00:07:06,840 --> 00:07:07,290 Yes. 119 00:07:07,290 --> 00:07:08,760 If it's pleasant, yes, then. 120 00:07:09,750 --> 00:07:15,750 So answer is containing, if not the second character, logic, and this president and this president 121 00:07:15,750 --> 00:07:22,120 then so abandoned now, Jack or so or is present, but always not presented at Waterloo. 122 00:07:22,410 --> 00:07:28,560 So this is will the condition of the current character, which is all so always present in this, but 123 00:07:28,580 --> 00:07:29,590 always not present here. 124 00:07:29,610 --> 00:07:34,470 So this condition will become true and I will have done my answer, which is fairly simple. 125 00:07:35,890 --> 00:07:37,950 OK, then this will be used. 126 00:07:38,050 --> 00:07:41,740 So suppose all the strings are same, all the strings at ABC. 127 00:07:43,460 --> 00:07:48,420 All listings at ABC, so in that case, this will never be executed, OK? 128 00:07:48,470 --> 00:07:52,130 This condition will never get executed and it will be my prefix. 129 00:07:52,130 --> 00:07:53,810 My prefix will be ABC only. 130 00:07:54,290 --> 00:07:57,630 So then this condition, then this line will be executed. 131 00:07:57,650 --> 00:07:58,460 OK, simple. 132 00:07:59,940 --> 00:08:01,580 Now, let's try to sum it up called. 133 00:08:09,390 --> 00:08:13,990 OK, so basically, if this is somebody basically if it does not exist. 134 00:08:14,010 --> 00:08:17,220 So what we can do, we can write a condition here. 135 00:08:18,290 --> 00:08:19,340 So basically. 136 00:08:22,320 --> 00:08:24,090 If string darts size is zero. 137 00:08:28,540 --> 00:08:33,820 We can return and protesting, OK, so basically we can get an answer, as says, containing empty string, 138 00:08:34,840 --> 00:08:37,120 or you can also write and protesting here also. 139 00:08:37,789 --> 00:08:38,140 OK. 140 00:08:44,420 --> 00:08:49,190 I guess our code is working fine now if you don't want to find out what you can do. 141 00:08:50,630 --> 00:08:51,800 Suppose you do not. 142 00:08:53,380 --> 00:08:56,330 Want to find out the minimum element so what we can do? 143 00:08:57,870 --> 00:09:00,340 We can take the first string as the minimum element. 144 00:09:00,480 --> 00:09:06,500 OK, so setting aside everything with him, what I will do, I do not want to find out the minimum element 145 00:09:06,570 --> 00:09:10,650 or let's say the minimum element is basically the first string. 146 00:09:10,650 --> 00:09:13,830 OK, first string is basically the smallest string. 147 00:09:15,160 --> 00:09:17,110 So this will be statis. 148 00:09:19,280 --> 00:09:25,430 OK, so the first string is basically the minimum string, OK, then again, Armatrading. 149 00:09:25,970 --> 00:09:29,900 Now, what do you have to do since you have assumed so it will start from one. 150 00:09:29,900 --> 00:09:31,850 OK, Jabel, start from one. 151 00:09:32,820 --> 00:09:34,650 And you are comparing the eight, correct? 152 00:09:34,860 --> 00:09:38,010 OK, so you are comparing the eighth character of the string. 153 00:09:38,430 --> 00:09:41,610 So you have to check first whether they exist or not. 154 00:09:41,640 --> 00:09:44,250 OK, so you have to check first. 155 00:09:44,640 --> 00:09:46,830 So if the eight character is basically. 156 00:09:47,910 --> 00:09:49,090 They're denied access to. 157 00:09:51,680 --> 00:09:52,550 Stringy. 158 00:09:54,610 --> 00:10:00,290 Darkland, you can use Daudt, Lenthall, you can use Dart based, OK, what I've seen, so suppose 159 00:10:00,290 --> 00:10:01,370 I'm using Darcis. 160 00:10:04,780 --> 00:10:07,720 So in that case, also, you will retain your answer. 161 00:10:07,780 --> 00:10:09,970 OK, so what I'm doing here. 162 00:10:12,160 --> 00:10:16,760 So I'm assuming the first string is basically the smallest string. 163 00:10:16,780 --> 00:10:23,110 OK, so this is not this, I am assuming the first dusting is basically the smallest string now I over 164 00:10:23,120 --> 00:10:27,070 the smallest string, but since this is not the smallest thing. 165 00:10:27,280 --> 00:10:32,560 So that's why you have to write this condition, you have to check whether the eighth character exists 166 00:10:32,560 --> 00:10:32,980 or not. 167 00:10:33,010 --> 00:10:39,340 OK, in this case, you do not have to write this condition because the string s was the minimum string 168 00:10:39,730 --> 00:10:40,930 string as well as many strings. 169 00:10:40,930 --> 00:10:42,210 So they are yet corrected. 170 00:10:42,580 --> 00:10:44,950 So they will always exist. 171 00:10:45,400 --> 00:10:47,110 OK, I will always exist. 172 00:10:47,110 --> 00:10:52,410 But here String S is not the smallest string, so you have to check the character exists or not. 173 00:10:52,420 --> 00:10:55,240 Otherwise you will get runtime error at this point. 174 00:10:55,650 --> 00:10:58,360 OK, if the character does not exist. 175 00:10:59,940 --> 00:11:01,950 So this is the only change that we have to do. 176 00:11:04,120 --> 00:11:05,710 OK, so this is the only change. 177 00:11:06,950 --> 00:11:08,110 Now let's meet our cool. 178 00:11:11,750 --> 00:11:13,670 So this is not demeaning string. 179 00:11:15,480 --> 00:11:17,880 OK, so what is their time in the space complexity? 180 00:11:19,110 --> 00:11:25,270 So basically the time complexities, let's say, over time complexities, Eman. 181 00:11:25,650 --> 00:11:28,320 So what is M m is basically the. 182 00:11:29,240 --> 00:11:36,710 Land of the smallest string, OK, and is basically the land of the smallest string and what is and 183 00:11:37,070 --> 00:11:39,570 so and is basically total number of strings. 184 00:11:39,590 --> 00:11:43,200 OK, this is vector nazis' number, total number of strings. 185 00:11:43,220 --> 00:11:47,230 OK, so this is due to M. 186 00:11:47,420 --> 00:11:51,070 OK, this is M letter, the smallest string and the inner loop. 187 00:11:51,110 --> 00:11:52,390 This is the number of string. 188 00:11:52,760 --> 00:11:54,120 So time complexities and. 189 00:11:55,780 --> 00:11:57,110 What is this space complexity? 190 00:11:57,130 --> 00:12:04,660 So if we are considering this space technology space taken by the existing so space is basically big 191 00:12:04,660 --> 00:12:07,360 off M OK, in the worst case, it will be big of him. 192 00:12:08,510 --> 00:12:11,980 OK, so this is the time complexity and this is the space complexity. 193 00:12:12,340 --> 00:12:14,570 So this was just an implementation problem. 194 00:12:15,010 --> 00:12:20,920 We are doing character by character imaging, so if you have any doubt in this question, you can ask 195 00:12:20,920 --> 00:12:21,070 me. 196 00:12:21,070 --> 00:12:22,150 OK, thank you.