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.

