1
00:00:00,650 --> 00:00:01,730
Welcome back.

2
00:00:01,730 --> 00:00:04,820
Let's now think about how we can solve this question.

3
00:00:04,820 --> 00:00:07,880
First, let's think about the brute force method.

4
00:00:07,880 --> 00:00:11,450
We could identify all the possible substrings.

5
00:00:11,450 --> 00:00:18,500
For example substrings of length one character, substrings of length two character substrings of length

6
00:00:18,500 --> 00:00:24,140
three characters, etc., and up to substrings of the length of the given string.

7
00:00:24,140 --> 00:00:25,550
This would be the last string, right?

8
00:00:25,550 --> 00:00:32,480
So that is one way we could just find all the substrings which are possible, and from all the substrings

9
00:00:32,480 --> 00:00:37,070
we can identify the substrings which are made up of unique characters.

10
00:00:37,070 --> 00:00:44,000
And then among those substrings we can find the substring of maximum length, identify its length and

11
00:00:44,000 --> 00:00:44,540
return it.

12
00:00:44,540 --> 00:00:47,900
So this would be the brute force method of solving this question.

13
00:00:47,900 --> 00:00:51,440
Now what would be the time complexity of this method?

14
00:00:51,440 --> 00:00:59,390
We know that if we have a string of length n, then the number of substrings that string would have

15
00:00:59,390 --> 00:01:01,730
will be of the order of n square.

16
00:01:01,730 --> 00:01:02,390
Why is that?

17
00:01:02,390 --> 00:01:04,160
So let's take an example.

18
00:01:04,160 --> 00:01:06,920
Let's say we have a string a, b, c, d, e.

19
00:01:07,160 --> 00:01:11,540
Now I can have five substrings of length one, right?

20
00:01:11,540 --> 00:01:14,900
I can have four substrings of length two.

21
00:01:14,930 --> 00:01:22,040
That is a, b, b, c, c, d, and d I can have three substrings of length three, a, b, c, b,

22
00:01:22,040 --> 00:01:28,430
c, d and c, d, e, etc. and finally I will have one substring of length five over here.

23
00:01:28,430 --> 00:01:28,700
Right.

24
00:01:28,700 --> 00:01:32,120
So five plus four plus three plus two plus one.

25
00:01:32,120 --> 00:01:39,590
Now if I have a string of length n in that case the number of substrings would be one plus two plus

26
00:01:39,590 --> 00:01:41,300
three etc. up to n.

27
00:01:41,300 --> 00:01:42,590
So that is what we have seen over here.

28
00:01:42,590 --> 00:01:42,890
Right?

29
00:01:42,890 --> 00:01:46,880
So we know that this is nothing but n into n plus one by two.

30
00:01:46,910 --> 00:01:53,990
So if I have a string of length n then the number of substrings that I have that I can make from that

31
00:01:53,990 --> 00:01:57,290
string would be n into n plus one by two.

32
00:01:57,290 --> 00:02:01,160
And when you simplify this, you will see that you will have an n square term.

33
00:02:01,160 --> 00:02:01,340
Right.

34
00:02:01,340 --> 00:02:03,530
So this is n square plus n by two.

35
00:02:03,560 --> 00:02:08,870
So we can say that the number of substrings will be of the order of n square.

36
00:02:09,470 --> 00:02:09,950
All right.

37
00:02:09,980 --> 00:02:16,790
Now after we have taken into consideration all the possible substrings, we need to identify the substrings

38
00:02:16,790 --> 00:02:18,110
of unique characters.

39
00:02:18,110 --> 00:02:24,380
So for each of the substring that we have identified, we have to do an upper bound of n operations

40
00:02:24,380 --> 00:02:25,760
to traverse it.

41
00:02:25,760 --> 00:02:29,060
So identifying the substrings of unique characters.

42
00:02:29,060 --> 00:02:33,500
So when we reach over here we will have done o of n cube operations.

43
00:02:33,500 --> 00:02:33,800
Right.

44
00:02:33,800 --> 00:02:36,650
So the time complexity will be O of n cube.

45
00:02:36,650 --> 00:02:39,740
And among them we just have to identify the maximum length.

46
00:02:39,740 --> 00:02:43,550
So we clearly can see that this is not an optimal solution.

47
00:02:43,550 --> 00:02:48,950
Let's try to think about a method with which we can do this in a much better time.

48
00:02:48,950 --> 00:02:49,760
Complexity.

49
00:02:49,760 --> 00:02:52,010
Now, you may have already thought about this.

50
00:02:52,010 --> 00:02:54,290
Let's say this is the string which is given to us.

51
00:02:54,290 --> 00:02:59,690
We can just use a simple hash table to store when we encounter a character.

52
00:02:59,690 --> 00:03:01,820
Like for example, we have B over here.

53
00:03:01,820 --> 00:03:08,780
Now as we traverse this string which is given to us when we come to this place, we can see that a B

54
00:03:08,780 --> 00:03:11,690
already was there because we are storing it in a hash table.

55
00:03:11,690 --> 00:03:15,320
So this would be the best way by which we can solve this.

56
00:03:15,320 --> 00:03:21,530
So we are going to store in a hash table whenever we are going to encounter a character, and we are

57
00:03:21,530 --> 00:03:23,810
going to store the index of that character.

58
00:03:23,810 --> 00:03:24,290
Why is that?

59
00:03:24,290 --> 00:03:27,590
So let's say we are we are traversing in this direction.

60
00:03:27,590 --> 00:03:29,990
So we have p q b r s t.

61
00:03:29,990 --> 00:03:34,190
So at this point we have already identified a substring of length six.

62
00:03:34,190 --> 00:03:35,690
Now again we come to B.

63
00:03:35,690 --> 00:03:41,690
Right now at this point we have to move the starting to this character over here.

64
00:03:41,690 --> 00:03:46,370
Because if I continue if I if I take this B then I cannot take this B right.

65
00:03:46,370 --> 00:03:47,810
So I cannot go to the right.

66
00:03:47,810 --> 00:03:54,410
So I have to move my starting point to the next index after what is there over here.

67
00:03:54,410 --> 00:03:55,880
And then I keep counting.

68
00:03:55,880 --> 00:03:59,600
So I have r s t b u v w p.

69
00:03:59,600 --> 00:04:01,550
So all of these can be taken together.

70
00:04:01,550 --> 00:04:01,850
Right.

71
00:04:01,850 --> 00:04:04,910
So this is how we are going to solve this question.

72
00:04:04,910 --> 00:04:11,450
So point number one we are going to store in a hash table whenever we encounter a new character.

73
00:04:11,450 --> 00:04:15,110
And we are going to store the index of that character in the given string.

74
00:04:15,110 --> 00:04:20,630
Now when we encounter a character which already was there previously, we will know because we will

75
00:04:20,630 --> 00:04:24,020
see that that particular key is there in the hash table.

76
00:04:24,020 --> 00:04:28,460
Now, in that case, we will have to decide whether we have to move our start.

77
00:04:28,460 --> 00:04:30,860
Because again, why is there a decision?

78
00:04:31,250 --> 00:04:34,130
For example, we have a P over here right now.

79
00:04:34,130 --> 00:04:39,020
You can see that because we had a B over here, we moved the start to this this place.

80
00:04:39,020 --> 00:04:41,960
So we are only considering strings starting from R.

81
00:04:41,990 --> 00:04:47,870
Now if we see a P just because there was a P earlier, we don't need to move the start to this place,

82
00:04:47,870 --> 00:04:51,410
which is before the place where the current start is.

83
00:04:51,410 --> 00:04:52,670
So that is not required, right?

84
00:04:52,670 --> 00:04:56,390
Because in that case again we'll have two B's in between.

85
00:04:56,390 --> 00:05:00,110
If we are going to take the start from here and something the end is.

86
00:05:00,210 --> 00:05:00,810
Somewhere over here.

87
00:05:01,080 --> 00:05:01,380
All right.

88
00:05:01,380 --> 00:05:03,630
So this is just developing an intuition.

89
00:05:03,630 --> 00:05:09,120
So point number one we are going to store in the hash table whenever we encounter a character.

90
00:05:09,120 --> 00:05:14,670
And when we encounter a character for the second time, we are going to decide whether we need to move

91
00:05:14,670 --> 00:05:16,230
the start pointer or not.

92
00:05:16,230 --> 00:05:22,740
And we will make an operation on the hash table so that we keep track where the particular character

93
00:05:22,740 --> 00:05:23,220
occurred.

94
00:05:23,220 --> 00:05:25,770
Latest in the string which is given to us.

95
00:05:25,770 --> 00:05:26,280
All right.

96
00:05:26,280 --> 00:05:27,750
So this is the intuition.

97
00:05:27,750 --> 00:05:34,200
Now let's just trace the algorithm and see what's happening to develop a good understanding of this

98
00:05:34,200 --> 00:05:34,740
approach.

99
00:05:34,740 --> 00:05:37,740
So again we are going to have a variable start.

100
00:05:37,740 --> 00:05:40,950
So it's going to point at the index zero in the beginning.

101
00:05:40,950 --> 00:05:42,480
And we need a variable.

102
00:05:42,480 --> 00:05:43,590
Let's call it max.

103
00:05:43,590 --> 00:05:46,410
So over here we will initialize it to zero.

104
00:05:46,410 --> 00:05:54,120
And then as we get uh substrings of longer length with unique characters we will just keep updating

105
00:05:54,120 --> 00:05:55,110
this value over here.

106
00:05:55,110 --> 00:05:57,810
And we also need a hash table.

107
00:05:57,810 --> 00:05:59,070
Let's call it scene.

108
00:05:59,070 --> 00:06:02,280
And initially this hash table is going to be empty.

109
00:06:02,760 --> 00:06:06,840
Now let me go ahead and write the indices of this string over here.

110
00:06:06,990 --> 00:06:07,530
All right.

111
00:06:07,560 --> 00:06:11,760
Now to traverse the given string we will need a variable.

112
00:06:11,760 --> 00:06:13,230
And let's call it I.

113
00:06:13,230 --> 00:06:15,600
And I is pointing to zero at this point.

114
00:06:15,780 --> 00:06:19,260
Now we are going to see whether P is there in our hash table.

115
00:06:19,260 --> 00:06:22,350
At the present moment we can see that it is not there.

116
00:06:22,350 --> 00:06:25,200
So we are going to make an entry into our hash table.

117
00:06:25,200 --> 00:06:31,230
The key is going to be p and the value is going to be this index over here which is zero.

118
00:06:31,470 --> 00:06:35,070
Now we can see that we have identified a substring.

119
00:06:35,070 --> 00:06:39,750
This over here which is of length one and length one is greater than zero.

120
00:06:39,750 --> 00:06:42,210
So let's update max to one.

121
00:06:42,420 --> 00:06:42,900
All right.

122
00:06:42,930 --> 00:06:44,280
Now let's move I.

123
00:06:44,310 --> 00:06:48,000
So we move I ahead and I is pointing to one at this point.

124
00:06:48,030 --> 00:06:50,910
Now we have the character Q over here.

125
00:06:50,910 --> 00:06:53,370
Now Q is not there in our hash table.

126
00:06:53,370 --> 00:06:57,720
So let's make an entry Q and the value is going to be one which is this one.

127
00:06:57,720 --> 00:06:58,290
Over here.

128
00:06:58,290 --> 00:07:04,320
Now we have identified a substring p q and the length of this substring is two which is greater than

129
00:07:04,320 --> 00:07:04,680
one.

130
00:07:04,680 --> 00:07:06,870
So let's update max to two.

131
00:07:07,620 --> 00:07:08,040
All right.

132
00:07:08,070 --> 00:07:09,960
Now again, let's move AI forward.

133
00:07:09,960 --> 00:07:11,880
So AI is pointing to two now.

134
00:07:11,880 --> 00:07:15,480
And we have identified a substring PCB.

135
00:07:15,510 --> 00:07:17,700
B is not there in our hash table.

136
00:07:17,700 --> 00:07:19,560
So let's make an entry too.

137
00:07:19,560 --> 00:07:23,160
And we update max to three because this is of length three.

138
00:07:24,380 --> 00:07:25,940
All right, now let's proceed.

139
00:07:25,940 --> 00:07:27,080
We move I ahead.

140
00:07:27,080 --> 00:07:32,360
So I is pointing to are at this point and we can see that this is not there in our hash table.

141
00:07:32,360 --> 00:07:33,920
So let's make an entry.

142
00:07:33,920 --> 00:07:39,590
Ah and three and again we have identified a substring of length four which is greater than three.

143
00:07:39,590 --> 00:07:40,730
So let's update it.

144
00:07:40,730 --> 00:07:42,020
And we have four over here.

145
00:07:42,020 --> 00:07:43,670
And we move ahead.

146
00:07:43,670 --> 00:07:46,460
Now I is pointing to the character S right.

147
00:07:46,460 --> 00:07:49,760
So again we do not have it in our hash table.

148
00:07:49,760 --> 00:07:51,650
So we make this entry S four.

149
00:07:51,650 --> 00:07:54,290
And we have identified a substring of length five.

150
00:07:54,290 --> 00:07:57,860
So we change max to five and we move forward.

151
00:07:57,860 --> 00:08:00,050
So now I is pointing to five.

152
00:08:00,080 --> 00:08:04,070
The character over here is T t is not there in our hash table.

153
00:08:04,070 --> 00:08:05,330
So let's make an entry.

154
00:08:05,330 --> 00:08:11,900
And we update max to six because we have identified this substring which is made up of unique characters.

155
00:08:11,900 --> 00:08:12,500
All right.

156
00:08:12,500 --> 00:08:13,970
Now the fun happens.

157
00:08:13,970 --> 00:08:19,790
Now when we move I, we encounter a character which is already there in our hash table.

158
00:08:19,790 --> 00:08:20,030
Right?

159
00:08:20,030 --> 00:08:26,330
We can see that B two is already there in our hash table, and that is the character at index six.

160
00:08:26,360 --> 00:08:31,310
Now we have to decide whether we need to move the start or not.

161
00:08:31,310 --> 00:08:38,390
So at this point start is actually before occurring before the previous occurrence of B.

162
00:08:38,390 --> 00:08:41,000
So that is why we will have to move start right.

163
00:08:41,000 --> 00:08:45,500
Because if you don't move start, then we will not be able to form a substring of unique characters

164
00:08:45,500 --> 00:08:47,480
because this B will come in between.

165
00:08:47,480 --> 00:08:47,750
Right?

166
00:08:47,750 --> 00:08:50,180
So we should not have this b anymore.

167
00:08:50,180 --> 00:08:52,400
That's why we need to move start now.

168
00:08:52,400 --> 00:08:53,510
How do we check this.

169
00:08:53,510 --> 00:08:55,040
How does the code do this.

170
00:08:55,070 --> 00:09:02,270
We will check whether start is greater or this B this index over here plus one which is three is great

171
00:09:02,270 --> 00:09:02,990
is greater.

172
00:09:02,990 --> 00:09:09,950
So start will be equal to the maximum between the previous value of start and two plus one where this

173
00:09:09,950 --> 00:09:16,520
two over here is the value which we have in our hash table for the key B and that is this two over here.

174
00:09:16,520 --> 00:09:16,880
All right.

175
00:09:16,880 --> 00:09:23,180
So the next index after this two which is the previous occurrence of character b the next index after

176
00:09:23,180 --> 00:09:24,440
this which is two plus one.

177
00:09:24,440 --> 00:09:25,550
That's three.

178
00:09:25,550 --> 00:09:28,640
And start currently is equal to zero which is this.

179
00:09:28,640 --> 00:09:29,120
Over here.

180
00:09:29,120 --> 00:09:33,950
Now in this case we can visually see start is before this two.

181
00:09:33,950 --> 00:09:34,400
Right.

182
00:09:34,400 --> 00:09:37,160
So therefore we have to move start.

183
00:09:37,160 --> 00:09:40,250
And we have checked it by this pseudo code.

184
00:09:40,250 --> 00:09:41,300
Over here we are.

185
00:09:41,300 --> 00:09:45,350
We are checking between start and the value at the key.

186
00:09:45,380 --> 00:09:48,200
The key B which is the character plus one.

187
00:09:48,200 --> 00:09:51,380
So two plus one and start among these two three is greater.

188
00:09:51,380 --> 00:09:53,390
So we have to move start.

189
00:09:53,390 --> 00:09:55,520
So let's move start to three.

190
00:09:55,520 --> 00:09:56,900
So we move start over here.

191
00:09:56,900 --> 00:10:00,710
And you can see that by doing this we have avoided this right.

192
00:10:00,710 --> 00:10:02,330
So we have avoided taking B.

193
00:10:02,330 --> 00:10:07,700
So we can go ahead and check for a longer substring with unique characters.

194
00:10:07,760 --> 00:10:09,170
So let's proceed.

195
00:10:09,590 --> 00:10:11,660
And again B is already there.

196
00:10:11,660 --> 00:10:13,850
So we don't need to make a new entry.

197
00:10:13,850 --> 00:10:19,220
But we have to update this value over here because we want the latest occurrence of B.

198
00:10:19,220 --> 00:10:21,710
And at the same time what about Max.

199
00:10:21,710 --> 00:10:25,070
Now at this point start is over here and I is over here.

200
00:10:25,070 --> 00:10:28,190
So the substring which we have is only of length four.

201
00:10:28,190 --> 00:10:29,900
But this is length six right.

202
00:10:29,900 --> 00:10:31,490
So we don't update max.

203
00:10:31,490 --> 00:10:33,140
Max is still six.

204
00:10:33,140 --> 00:10:36,800
But as we discussed we have to update this 2 to 6 over here.

205
00:10:36,800 --> 00:10:39,740
So six is the latest occurrence of B.

206
00:10:39,740 --> 00:10:41,480
That is why we have to update this.

207
00:10:41,480 --> 00:10:42,080
All right.

208
00:10:42,110 --> 00:10:43,250
Now let's proceed.

209
00:10:43,250 --> 00:10:44,990
We again shift I ahead.

210
00:10:44,990 --> 00:10:47,720
So I is now pointing to index seven.

211
00:10:47,720 --> 00:10:51,740
We have you over here and you is not there in our hash table.

212
00:10:51,740 --> 00:10:55,760
So we make an entry you and seven seven is the index over here.

213
00:10:55,760 --> 00:10:58,730
And let's check the string r s t b u.

214
00:10:58,730 --> 00:10:59,960
This is of length five.

215
00:10:59,960 --> 00:11:03,230
But we have already identified a substring of length six.

216
00:11:03,230 --> 00:11:04,520
So we don't change this.

217
00:11:04,520 --> 00:11:05,720
And we move ahead.

218
00:11:05,750 --> 00:11:11,390
Now I is pointing to index eight and v is not there in our hash table.

219
00:11:11,390 --> 00:11:13,280
So let's make an entry v eight.

220
00:11:13,280 --> 00:11:14,930
And what about the substring.

221
00:11:14,930 --> 00:11:16,820
The substring is of length six.

222
00:11:16,820 --> 00:11:17,990
So that is what we have.

223
00:11:17,990 --> 00:11:19,400
We already have over here.

224
00:11:19,400 --> 00:11:21,050
So we don't update this right.

225
00:11:21,050 --> 00:11:22,490
Again we move forward.

226
00:11:22,490 --> 00:11:26,840
Now we have w w is not there in our hash table.

227
00:11:26,840 --> 00:11:33,380
We make an entry and we change max because now we have identified a substring of length seven.

228
00:11:33,380 --> 00:11:33,710
Right.

229
00:11:33,710 --> 00:11:36,770
So max at this point is equal to seven.

230
00:11:36,770 --> 00:11:41,180
Now again we move I forward and we encounter p.

231
00:11:42,430 --> 00:11:45,730
And we have already encountered P previously.

232
00:11:45,730 --> 00:11:53,170
So we can see that when we look at our hash table, P is already there and the key is p and the value

233
00:11:53,170 --> 00:11:54,130
is zero.

234
00:11:54,160 --> 00:11:58,180
Now again we have to decide whether we need to move start or not.

235
00:11:58,210 --> 00:12:02,260
Now over here we can see that start is already ahead of this.

236
00:12:02,260 --> 00:12:02,560
Right.

237
00:12:02,560 --> 00:12:04,750
So this index is over here.

238
00:12:04,780 --> 00:12:07,480
Now we can see that start is already ahead of it.

239
00:12:07,480 --> 00:12:09,670
So there is no point in moving it back.

240
00:12:09,730 --> 00:12:10,210
Right.

241
00:12:10,210 --> 00:12:10,900
Logically.

242
00:12:10,900 --> 00:12:15,340
So that is what is done by the check that we have put in the code.

243
00:12:15,340 --> 00:12:20,440
We will check whether start is greater or this index plus one is greater.

244
00:12:20,440 --> 00:12:26,920
So we will say that start is equal to max between start and this zero over here plus one.

245
00:12:26,920 --> 00:12:32,170
Now at this point start is equal to three and zero plus one is equal to one.

246
00:12:33,290 --> 00:12:35,900
So among three and one three is greater.

247
00:12:35,900 --> 00:12:38,060
So we don't need to move start right.

248
00:12:38,060 --> 00:12:43,880
And we can see that we have identified a substring of length equal to eight.

249
00:12:43,880 --> 00:12:45,590
So let's update the length.

250
00:12:45,590 --> 00:12:47,090
And we have eight over here.

251
00:12:47,090 --> 00:12:48,890
And we move forward.

252
00:12:50,020 --> 00:12:50,410
All right.

253
00:12:50,410 --> 00:12:55,150
And again remember this over here has to be updated to ten which is the latest occurrence of P.

254
00:12:55,420 --> 00:12:55,840
All right.

255
00:12:55,870 --> 00:12:57,610
Now we move again I forward.

256
00:12:57,610 --> 00:13:03,400
Now at this point we have V and we can see that V is there in our hash table over here.

257
00:13:03,400 --> 00:13:03,700
Right.

258
00:13:03,700 --> 00:13:06,760
So therefore again we have to decide whether we have to move.

259
00:13:06,760 --> 00:13:12,430
Start now in this case this occurrence of V is ahead of what start is currently right.

260
00:13:12,430 --> 00:13:14,230
Therefore yes we have to move it.

261
00:13:14,230 --> 00:13:20,740
And to check this we are going to say start is max between Start and this eight over here, which is

262
00:13:20,740 --> 00:13:24,760
the value currently in our hash table for the key V plus one.

263
00:13:24,760 --> 00:13:28,480
So start is three and eight plus one is equal to nine.

264
00:13:28,480 --> 00:13:30,700
So yes we have to move it to nine.

265
00:13:30,700 --> 00:13:32,260
So we move start to nine.

266
00:13:32,260 --> 00:13:37,150
And then again over here the length of the substring is just three.

267
00:13:37,150 --> 00:13:38,410
So we don't update.

268
00:13:38,410 --> 00:13:40,990
And we keep max at eight itself.

269
00:13:40,990 --> 00:13:42,310
And then we move forward.

270
00:13:42,310 --> 00:13:46,900
And again over here we have to update V to the latest occurrence which is 11.

271
00:13:46,900 --> 00:13:48,760
So this has to be changed to 11.

272
00:13:48,760 --> 00:13:50,950
So this eight has to be changed to 11.

273
00:13:50,950 --> 00:13:52,360
And then we move forward.

274
00:13:52,360 --> 00:13:54,340
So again we have y over here.

275
00:13:54,340 --> 00:13:55,990
It's not there in our hash table.

276
00:13:55,990 --> 00:13:58,390
So we make an entry y 12.

277
00:13:58,510 --> 00:14:00,070
And that is the end right.

278
00:14:00,070 --> 00:14:02,890
So again this length is four which is not greater than eight.

279
00:14:02,890 --> 00:14:04,510
So we stay at eight.

280
00:14:04,510 --> 00:14:06,310
And that gives us the answer.

281
00:14:06,310 --> 00:14:06,820
All right.

282
00:14:06,820 --> 00:14:08,740
And then we just have to return eight.

283
00:14:08,740 --> 00:14:09,820
And that is the answer.

284
00:14:09,820 --> 00:14:14,860
Now let's quickly look at the complexity analysis of this solution that we discussed.

285
00:14:14,860 --> 00:14:19,330
The time complexity of this solution is clearly o of n right.

286
00:14:19,330 --> 00:14:22,450
It's just an order of n where n is the length of the string.

287
00:14:22,450 --> 00:14:26,530
Because we can see that we just had to traverse the given string once.

288
00:14:26,530 --> 00:14:28,900
So we're just iterating through the string.

289
00:14:29,410 --> 00:14:36,850
And for each value of I we are just doing a set of constant time operations, which is things like changing

290
00:14:36,850 --> 00:14:41,860
the start, accessing or updating values from a hash table and comparing the length.

291
00:14:41,860 --> 00:14:45,550
Now all of these are just constant time operations, right?

292
00:14:45,550 --> 00:14:48,490
Again, remember that's the advantage of a hash table, right?

293
00:14:48,490 --> 00:14:53,710
If you have a key you can access or update values in the hash table in constant time.

294
00:14:53,710 --> 00:14:59,170
So we are making use of this property to solve this question in the optimal time complexity.

295
00:14:59,170 --> 00:15:03,370
So we have seen that the time complexity of this solution is O of n.

296
00:15:03,370 --> 00:15:06,550
Now what about the space complexity of this solution?

297
00:15:06,550 --> 00:15:13,390
Now we can say that the space complexity of the solution will depend on the size of our hash table seen.

298
00:15:13,390 --> 00:15:13,810
Right.

299
00:15:13,810 --> 00:15:16,330
So let's try to think about this.

300
00:15:16,690 --> 00:15:21,070
Let's say the given string is of length n.

301
00:15:21,070 --> 00:15:26,770
And let's say m is the number of unique characters which is used in the string.

302
00:15:26,770 --> 00:15:33,790
So therefore we can say that if if m is the number of unique characters used, then the space complexity

303
00:15:33,790 --> 00:15:35,080
will be just m, right?

304
00:15:35,080 --> 00:15:42,070
So the space complexity is of the order of the minimum between n and m, where m is the number of unique

305
00:15:42,070 --> 00:15:42,970
characters used.

306
00:15:43,000 --> 00:15:49,960
Now, if all the characters are unique, then we can say that the space complexity is O of N, so that's

307
00:15:49,960 --> 00:15:51,490
the space complexity.

308
00:15:51,490 --> 00:15:54,070
And again remember that's because the hash table, right?

309
00:15:54,070 --> 00:15:57,280
We are only storing unique characters in our hash table.

310
00:15:57,280 --> 00:16:04,210
So the time complexity is O of n and the space complexity is O of the minimum between n and m.