1
00:00:00,000 --> 00:00:02,920
TOMMY MACWILLIAM: So what we're
going to do is, given a string,

2
00:00:02,920 --> 00:00:07,080
we're going to be looking for the
length of the longest substring

3
00:00:07,080 --> 00:00:09,280
without repeating characters.

4
00:00:09,280 --> 00:00:16,050
So, for instance, if I gave you
the string abcabcbb, the length

5
00:00:16,050 --> 00:00:18,420
of the longest substring there is 3.

6
00:00:18,420 --> 00:00:21,450
So there's abc, where it doesn't have
any repeating characters in there.

7
00:00:21,450 --> 00:00:23,075
And there's a few other ones like that.

8
00:00:23,075 --> 00:00:24,783
So your function would
take that as input

9
00:00:24,783 --> 00:00:27,480
and then just return the length
of that string, which is 3.

10
00:00:27,480 --> 00:00:29,070
MARIA ZLATKOVA: Awesome.

11
00:00:29,070 --> 00:00:29,580
Hey, Tommy.

12
00:00:29,580 --> 00:00:29,920
How are you?

13
00:00:29,920 --> 00:00:30,180
TOMMY MACWILLIAM: Awesome.

14
00:00:30,180 --> 00:00:31,345
How's it going?

15
00:00:31,345 --> 00:00:32,220
MARIA ZLATKOVA: Good.

16
00:00:32,220 --> 00:00:33,420
How's your day going?

17
00:00:33,420 --> 00:00:34,545
TOMMY MACWILLIAM: I'm good.

18
00:00:34,545 --> 00:00:36,850
It's a sunny day still in San Francisco.

19
00:00:36,850 --> 00:00:37,647
So I'm loving it.

20
00:00:37,647 --> 00:00:38,730
MARIA ZLATKOVA: Beautiful.

21
00:00:38,730 --> 00:00:41,802
It's kind of a gloomy day in
New York but still pretty warm.

22
00:00:41,802 --> 00:00:42,942
So I'll take it.

23
00:00:42,942 --> 00:00:43,900
TOMMY MACWILLIAM: Nice.

24
00:00:43,900 --> 00:00:45,775
Well, thanks so much
for jumping on the call.

25
00:00:45,775 --> 00:00:48,260
Let's jump into a coding problem.

26
00:00:48,260 --> 00:00:49,260
MARIA ZLATKOVA: Awesome.

27
00:00:49,260 --> 00:00:49,680
TOMMY MACWILLIAM: All right.

28
00:00:49,680 --> 00:00:51,690
So it looks like you've
got the Replit set up.

29
00:00:51,690 --> 00:00:52,920
Notice you're set to Python.

30
00:00:52,920 --> 00:00:54,960
Is that the language you'd like to use?

31
00:00:54,960 --> 00:00:56,460
MARIA ZLATKOVA: Yep, that's
the language I'd like to use,

32
00:00:56,460 --> 00:00:57,480
if that sounds good with you.

33
00:00:57,480 --> 00:00:57,900
TOMMY MACWILLIAM: Perfect.

34
00:00:57,900 --> 00:00:59,290
That's good with me.

35
00:00:59,290 --> 00:01:00,518
MARIA ZLATKOVA: Cool.

36
00:01:00,518 --> 00:01:02,560
Just thinking through this
question a little bit,

37
00:01:02,560 --> 00:01:06,610
I guess a few clarifying questions.

38
00:01:06,610 --> 00:01:08,970
So we just want to
find the length, right?

39
00:01:08,970 --> 00:01:12,362
We don't care about returning
one or all of the subsequences

40
00:01:12,362 --> 00:01:13,320
that match that length.

41
00:01:13,320 --> 00:01:14,820
TOMMY MACWILLIAM: Yep, that's right.

42
00:01:14,820 --> 00:01:16,860
MARIA ZLATKOVA: Awesome, cool.

43
00:01:16,860 --> 00:01:18,930
And then when it comes
to the input, I see

44
00:01:18,930 --> 00:01:21,900
the example we have here is
all lowercase characters.

45
00:01:21,900 --> 00:01:25,410
Should we assume that we're going to
get all lowercase characters as input?

46
00:01:25,410 --> 00:01:27,702
Or do we want to handle
sanitizing that input?

47
00:01:27,702 --> 00:01:29,410
TOMMY MACWILLIAM:
That's a good question.

48
00:01:29,410 --> 00:01:31,590
You can assume the
input's all lowercase.

49
00:01:31,590 --> 00:01:33,720
MARIA ZLATKOVA: Awesome, cool.

50
00:01:33,720 --> 00:01:39,438
And I guess could then put be
empty, like the empty string.

51
00:01:39,438 --> 00:01:41,730
TOMMY MACWILLIAM: It could,
in which case you return 0.

52
00:01:41,730 --> 00:01:42,980
MARIA ZLATKOVA: Awesome, cool.

53
00:01:42,980 --> 00:01:44,840


54
00:01:44,840 --> 00:01:45,340
Great.

55
00:01:45,340 --> 00:01:47,440
I think that covered
all of my questions.

56
00:01:47,440 --> 00:01:49,790
So maybe then just give a few examples.

57
00:01:49,790 --> 00:01:55,840
So abcabcbb, the answer would be
3, the output that we want to give.

58
00:01:55,840 --> 00:02:01,390
If we have all repeating characters, the
output would be just 1, I'm assuming?

59
00:02:01,390 --> 00:02:02,890
TOMMY MACWILLIAM: Yep, that's right.

60
00:02:02,890 --> 00:02:04,180
MARIA ZLATKOVA: Awesome.

61
00:02:04,180 --> 00:02:07,390
And conversely, if we have
all different characters,

62
00:02:07,390 --> 00:02:10,300
the output would be 6 in this case.

63
00:02:10,300 --> 00:02:11,522
TOMMY MACWILLIAM: Yep.

64
00:02:11,522 --> 00:02:14,230
MARIA ZLATKOVA: And then, as we
said, if we get the empty string,

65
00:02:14,230 --> 00:02:15,150
the output would be 0.

66
00:02:15,150 --> 00:02:17,950


67
00:02:17,950 --> 00:02:18,580
Yeah, awesome.

68
00:02:18,580 --> 00:02:23,440
I think that makes a lot of sense to--

69
00:02:23,440 --> 00:02:27,170
when I'm looking at this
initial string and problem,

70
00:02:27,170 --> 00:02:30,520
I guess the first instinct that I
have for the very naive solution

71
00:02:30,520 --> 00:02:38,650
is that brute force, we can just
get all of the possible subsequences

72
00:02:38,650 --> 00:02:42,310
or substrings and check whether
there are any duplicate characters

73
00:02:42,310 --> 00:02:43,510
within those substrings.

74
00:02:43,510 --> 00:02:50,560
So in the abcabcbb example, that would
be first starting with every substring

75
00:02:50,560 --> 00:02:55,030
starting with a would be a and checking
if that has any repeating characters.

76
00:02:55,030 --> 00:02:58,000
Then ab-- it doesn't have
any duplicate characters.

77
00:02:58,000 --> 00:03:00,740
Then abc-- it also doesn't
have any duplicate characters.

78
00:03:00,740 --> 00:03:04,600
Then abca, which has
duplicate characters.

79
00:03:04,600 --> 00:03:07,420
And then every single
one-- abcab would also

80
00:03:07,420 --> 00:03:11,110
have duplicate characters, given
that the substring of that had them

81
00:03:11,110 --> 00:03:17,740
and also that b is repeating, similar
with abcabc, abcabcb, and abcabcbb.

82
00:03:17,740 --> 00:03:23,320
So it would be a very similar
case if we start at b and at c.

83
00:03:23,320 --> 00:03:27,550
So it's making me feel
like the naive solution,

84
00:03:27,550 --> 00:03:31,910
we'd be doing a little bit
of work that is not useful.

85
00:03:31,910 --> 00:03:35,290
So if we could avoid
that, that would be great.

86
00:03:35,290 --> 00:03:39,370
Reasoning a little bit over that
naive solution brute force approach,

87
00:03:39,370 --> 00:03:44,300
going through all possible
subsequences would be quadratic time.

88
00:03:44,300 --> 00:03:48,910
And then within that, checking
whether there are duplicate characters

89
00:03:48,910 --> 00:03:51,500
within each substring
would be linear time.

90
00:03:51,500 --> 00:03:56,500
So in total, that probably
would be n to the third.

91
00:03:56,500 --> 00:03:57,970
So that is not great.

92
00:03:57,970 --> 00:04:01,480
So I'm going to try to
optimize that if we can.

93
00:04:01,480 --> 00:04:06,850
And looking at this,
the way I described it,

94
00:04:06,850 --> 00:04:09,760
starting at different
points of the string,

95
00:04:09,760 --> 00:04:13,750
I'm starting to think maybe we
can have a range within the string

96
00:04:13,750 --> 00:04:17,740
that we track with a starting
index and an ending index.

97
00:04:17,740 --> 00:04:19,989
And maybe we can expand--

98
00:04:19,989 --> 00:04:22,615


99
00:04:22,615 --> 00:04:26,020
the start of string and expand
our ending index to the right.

100
00:04:26,020 --> 00:04:32,320
And the moment we encounter a duplicate
character or a repeating character,

101
00:04:32,320 --> 00:04:36,820
we start to move our
start index forward to try

102
00:04:36,820 --> 00:04:39,850
to get to a subsequence
that doesn't contain

103
00:04:39,850 --> 00:04:41,380
that duplicate character anymore.

104
00:04:41,380 --> 00:04:43,300
And all the while,
while we're doing that,

105
00:04:43,300 --> 00:04:47,950
keep track of the longest
encountered length.

106
00:04:47,950 --> 00:04:51,560
And I guess I have-- another
assumption question is,

107
00:04:51,560 --> 00:04:53,857
could we use an extra data
structure in this question?

108
00:04:53,857 --> 00:04:55,690
TOMMY MACWILLIAM: Yeah,
that's totally fine.

109
00:04:55,690 --> 00:04:57,850
I think that that sliding
window you're describing,

110
00:04:57,850 --> 00:05:00,190
that sounds like a pretty
good approach to me.

111
00:05:00,190 --> 00:05:00,560
MARIA ZLATKOVA: Awesome.

112
00:05:00,560 --> 00:05:02,380
Yeah, I think for that
sliding window, I'd

113
00:05:02,380 --> 00:05:10,600
like to use a HashSet so that we can
have pretty constant time in looking up

114
00:05:10,600 --> 00:05:14,980
how often certain characters
are within the string already.

115
00:05:14,980 --> 00:05:17,490
And we can do that lookup very quickly.

116
00:05:17,490 --> 00:05:19,240
TOMMY MACWILLIAM: Yeah,
that sounds great.

117
00:05:19,240 --> 00:05:20,240
MARIA ZLATKOVA: Awesome.

118
00:05:20,240 --> 00:05:23,800
So if that sounds good, I'm going
to go ahead and define our function.

119
00:05:23,800 --> 00:05:28,870
I'm going to call it length
of longest substring.

120
00:05:28,870 --> 00:05:32,200
We take in just one parameter,
I'm assuming, which is the string.

121
00:05:32,200 --> 00:05:33,340
TOMMY MACWILLIAM: Yep.

122
00:05:33,340 --> 00:05:38,580
MARIA ZLATKOVA: And then I need to
define the output, which is an integer.

123
00:05:38,580 --> 00:05:39,080
Cool.

124
00:05:39,080 --> 00:05:41,380
So as I said, would
love to use a HashSet.

125
00:05:41,380 --> 00:05:45,130
So I'm just going to
start by initializing it.

126
00:05:45,130 --> 00:05:50,708
And can just initialize it
all to 0's for now and count--

127
00:05:50,708 --> 00:05:53,500
we're going to count how many
occurrences of each character that we

128
00:05:53,500 --> 00:05:56,620
encounter happen within the substring.

129
00:05:56,620 --> 00:06:00,520
And I'm going to multiply
that by 128, because I

130
00:06:00,520 --> 00:06:05,450
know that we have 128 ASCII characters.

131
00:06:05,450 --> 00:06:09,640
So just to start off,
initialize it to that.

132
00:06:09,640 --> 00:06:13,270
And then going to
define the length, which

133
00:06:13,270 --> 00:06:15,570
we're going to want to track
of that longest substring,

134
00:06:15,570 --> 00:06:17,320
and define that to 0.

135
00:06:17,320 --> 00:06:19,330
Getting some-- ah.

136
00:06:19,330 --> 00:06:20,115
Oh, OK.

137
00:06:20,115 --> 00:06:21,490
Variable assigned but never used.

138
00:06:21,490 --> 00:06:24,190
That's OK, because we
haven't used it yet.

139
00:06:24,190 --> 00:06:28,450
And then going to use
the start and end index

140
00:06:28,450 --> 00:06:30,740
approach that I described
with that sliding window.

141
00:06:30,740 --> 00:06:32,860
So the start index--

142
00:06:32,860 --> 00:06:35,660
maybe I'll just call
it left for clarity.

143
00:06:35,660 --> 00:06:36,970
I'm going to assign that to 0.

144
00:06:36,970 --> 00:06:41,370
And then what we want to do first
is start going through the string.

145
00:06:41,370 --> 00:06:42,910
We can do it in a few ways.

146
00:06:42,910 --> 00:06:45,630
A while loop-- but maybe
I'll do a for loop to start.

147
00:06:45,630 --> 00:06:49,230
So can say for right--

148
00:06:49,230 --> 00:06:54,270
and right is referring to my end index,
which I described-- for right in range

149
00:06:54,270 --> 00:06:58,920
of the length of the string.

150
00:06:58,920 --> 00:07:00,760
Thankfully, saw Connor's
previous interview,

151
00:07:00,760 --> 00:07:03,270
so I now know that we
can [INAUDIBLE] here.

152
00:07:03,270 --> 00:07:07,260
But we have to do the
length of the string.

153
00:07:07,260 --> 00:07:14,260
And then the first thing I want to do
in this case is to make sure that--

154
00:07:14,260 --> 00:07:18,070
basically, what we
want to do is increment

155
00:07:18,070 --> 00:07:23,050
the count of the specific character
that we're at by 1 in the HashSet

156
00:07:23,050 --> 00:07:24,050
that we have.

157
00:07:24,050 --> 00:07:29,590
So the way we're going to do that
is we're going to say chars at s

158
00:07:29,590 --> 00:07:33,430
at index right, because s is our string.

159
00:07:33,430 --> 00:07:36,670
And we're going to increment that by 1.

160
00:07:36,670 --> 00:07:40,510
And that's OK because we've
defined all of the characters--

161
00:07:40,510 --> 00:07:46,640
all of the essentially fields
and our HashSet to be 0.

162
00:07:46,640 --> 00:07:47,140
Cool.

163
00:07:47,140 --> 00:07:52,340
So then the next thing I want to do
is I want to take care of that case

164
00:07:52,340 --> 00:07:56,260
which I mentioned earlier, which is
if we encounter a duplicate character,

165
00:07:56,260 --> 00:08:02,302
it's moving the left or the start
index forward until we don't

166
00:08:02,302 --> 00:08:03,760
have a duplicate character anymore.

167
00:08:03,760 --> 00:08:07,780
And since we're using
chars as our HashSet,

168
00:08:07,780 --> 00:08:11,080
the way that we know that we've
encountered more than one character

169
00:08:11,080 --> 00:08:21,110
is if chars at s index
right is greater than 1.

170
00:08:21,110 --> 00:08:24,810
And so I'm going to do a
while loop here because we

171
00:08:24,810 --> 00:08:28,470
could have multiple repeating
characters within the substring.

172
00:08:28,470 --> 00:08:33,659
So I want to make sure that I get rid
of all potential repeating characters.

173
00:08:33,659 --> 00:08:35,760
Or the repeating
character could actually

174
00:08:35,760 --> 00:08:37,380
be at a later point in the substring.

175
00:08:37,380 --> 00:08:40,770
So I want to get to that point
and make sure I move the start

176
00:08:40,770 --> 00:08:44,220
index by enough characters forward.

177
00:08:44,220 --> 00:08:49,200
So the way we're going
to do this is first we

178
00:08:49,200 --> 00:08:52,350
want to update the
count that we're keeping

179
00:08:52,350 --> 00:08:55,350
track of in our HashSet for
that specific character.

180
00:08:55,350 --> 00:09:00,630
So the way we're going to do that is
we're going to say chars at s at--

181
00:09:00,630 --> 00:09:03,220
I think I called it left--

182
00:09:03,220 --> 00:09:05,400
[INAUDIBLE] minus equals 1.

183
00:09:05,400 --> 00:09:08,610
And then what I'm going to do
is-- to move left forward--

184
00:09:08,610 --> 00:09:12,860
is I'm just going to increment left.

185
00:09:12,860 --> 00:09:13,360
Cool.

186
00:09:13,360 --> 00:09:16,530
And then one thing
which I haven't done yet

187
00:09:16,530 --> 00:09:21,160
is I want to make sure I'm keeping
track of the length, as we said earlier.

188
00:09:21,160 --> 00:09:27,280
So the length at the
first iteration will be--

189
00:09:27,280 --> 00:09:28,720
we've initialized it to 0.

190
00:09:28,720 --> 00:09:31,060
And then-- the first time we calculated.

191
00:09:31,060 --> 00:09:32,920
The length between two
indexes in a string

192
00:09:32,920 --> 00:09:37,360
typically is the ending index
minus the starting index plus 1,

193
00:09:37,360 --> 00:09:39,170
because strings are 0 index.

194
00:09:39,170 --> 00:09:42,840
So in our case, it's
right minus left plus 1.

195
00:09:42,840 --> 00:09:45,380
If I could spell correctly,
that would be great.

196
00:09:45,380 --> 00:09:50,680
And then what I'm going to do so that
we always keep track of the biggest--

197
00:09:50,680 --> 00:09:53,650
the maximum possible length is
I'm going to use the max function

198
00:09:53,650 --> 00:09:58,930
and say I want to take the max
of either the current length or--

199
00:09:58,930 --> 00:10:02,170
the length that we've been keeping
track of or the current length based

200
00:10:02,170 --> 00:10:03,850
on the right and left integers.

201
00:10:03,850 --> 00:10:09,820
And then the last thing we want
to do is return the length,

202
00:10:09,820 --> 00:10:14,210
because we want to return that integer.

203
00:10:14,210 --> 00:10:15,110
Cool.

204
00:10:15,110 --> 00:10:19,250
And I guess, just to
sanity check a little bit

205
00:10:19,250 --> 00:10:22,860
before I run this, just
going to do it with abca,

206
00:10:22,860 --> 00:10:26,360
because it's a little bit
shorter than abcabcbb.

207
00:10:26,360 --> 00:10:30,390
So abca should be 3,
the output for that.

208
00:10:30,390 --> 00:10:36,060
So what we're going to do is
when we start our for loop,

209
00:10:36,060 --> 00:10:41,340
we're going to say that
chars at a is equal to 1.

210
00:10:41,340 --> 00:10:43,110
We're going to add 1 to that.

211
00:10:43,110 --> 00:10:45,670
It's not greater than 1
in the first iteration.

212
00:10:45,670 --> 00:10:54,860
So what we're going to do is
just take the length and set it.

213
00:10:54,860 --> 00:10:59,240
And because right and left are 0 at
that first run through the for loop,

214
00:10:59,240 --> 00:11:00,770
it's going to be 0 minus 0 plus 1.

215
00:11:00,770 --> 00:11:02,720
So length is going to
be 1 at this stage.

216
00:11:02,720 --> 00:11:07,880
And then when we get to b, chars
at b is going to be granted to 1.

217
00:11:07,880 --> 00:11:10,032
Chars at b still is not greater than 1.

218
00:11:10,032 --> 00:11:11,990
So again, we're just
going to jump with length.

219
00:11:11,990 --> 00:11:17,870
And at this point, it's going to be
2, because 1 minus 0 plus 1 is 2.

220
00:11:17,870 --> 00:11:21,200
Then we're at index 2, which is
a third character, which is c.

221
00:11:21,200 --> 00:11:25,010
So again, setting chars at c to be 1.

222
00:11:25,010 --> 00:11:27,060
And then it's not greater than 1.

223
00:11:27,060 --> 00:11:30,290
So we just jump and then increment
the length again to 3 this time,

224
00:11:30,290 --> 00:11:34,165
because 2 minus 0 plus 1 is 3.

225
00:11:34,165 --> 00:11:36,290
And then in the final
run-through of that for loop,

226
00:11:36,290 --> 00:11:37,790
we're going to encounter a again.

227
00:11:37,790 --> 00:11:42,440
And so chars at a is now equal
to 2, which is greater than 1.

228
00:11:42,440 --> 00:11:44,910
So what we're going to
do is decrement that.

229
00:11:44,910 --> 00:11:47,090
So again, chars at a becomes 1.

230
00:11:47,090 --> 00:11:51,140
And we're going to move it forward--

231
00:11:51,140 --> 00:11:54,500
left, sorry-- our left index forward.

232
00:11:54,500 --> 00:12:05,910
And what we get now is that we want to
take the max of either 3 or 0, 1, 2, 3.

233
00:12:05,910 --> 00:12:09,390
So 1, 2, 3, which again is
going to give us length 3.

234
00:12:09,390 --> 00:12:12,443
And we've run through basically
all of the elements here.

235
00:12:12,443 --> 00:12:14,610
So what we're going to do
is just return line three.

236
00:12:14,610 --> 00:12:17,910
So just by running through this simple
example, I think this should work.

237
00:12:17,910 --> 00:12:20,830
And I'm going to write
out some test pieces.

238
00:12:20,830 --> 00:12:28,582
So maybe I'll just print input and
maybe just define our string here.

239
00:12:28,582 --> 00:12:29,707
The first will be abcabcbb.

240
00:12:29,707 --> 00:12:32,730


241
00:12:32,730 --> 00:12:35,760
Our input is going to be string.

242
00:12:35,760 --> 00:12:45,010
And then we want to say length is equal
to calling the function on string.

243
00:12:45,010 --> 00:12:54,330
And finally, print output to be length.

244
00:12:54,330 --> 00:12:55,470
Cool.

245
00:12:55,470 --> 00:12:57,000
So it may have some errors.

246
00:12:57,000 --> 00:13:00,450
I'm just going to run it through
the first time and see what happens.

247
00:13:00,450 --> 00:13:05,710
And I see here that on line
14, we have "lists indices must

248
00:13:05,710 --> 00:13:08,380
be integers or slices, not strings."

249
00:13:08,380 --> 00:13:11,333
So looking at line 14--

250
00:13:11,333 --> 00:13:14,500
oh, I think this is very interesting,
because I referred to ASCII characters

251
00:13:14,500 --> 00:13:17,980
in the beginning, but
then I didn't really

252
00:13:17,980 --> 00:13:23,440
take into account that we can't have
a character itself as the index.

253
00:13:23,440 --> 00:13:24,790
But we have to--

254
00:13:24,790 --> 00:13:26,802
I think we have to use
a function called ord.

255
00:13:26,802 --> 00:13:28,760
TOMMY MACWILLIAM MACWILLIAM:
Yep, that's right.

256
00:13:28,760 --> 00:13:29,065
MARIA ZLATKOVA: Awesome.

257
00:13:29,065 --> 00:13:31,630
Yeah, I think that function
returns an integer that

258
00:13:31,630 --> 00:13:33,290
represents the Unicode character.

259
00:13:33,290 --> 00:13:40,300
So what I want to do is I want to
wrap ord around every single time I'm

260
00:13:40,300 --> 00:13:41,815
using an index within chars.

261
00:13:41,815 --> 00:13:44,470


262
00:13:44,470 --> 00:13:48,660
Those should be all the times.

263
00:13:48,660 --> 00:13:51,610
And then input abcabcbb, output 3.

264
00:13:51,610 --> 00:13:52,180
That's great.

265
00:13:52,180 --> 00:13:55,560
I'm just going to run through
and add a few more test

266
00:13:55,560 --> 00:13:59,490
cases like the ones we mentioned.

267
00:13:59,490 --> 00:14:02,921
So bbb, abcdef.

268
00:14:02,921 --> 00:14:06,570


269
00:14:06,570 --> 00:14:07,070
Oh.

270
00:14:07,070 --> 00:14:09,860


271
00:14:09,860 --> 00:14:12,800
And maybe just add the empty
string for good measure

272
00:14:12,800 --> 00:14:17,750
to see if that gets us the right result.

273
00:14:17,750 --> 00:14:18,290
Cool.

274
00:14:18,290 --> 00:14:23,690
So we get input bbb,
output 1, which is great.

275
00:14:23,690 --> 00:14:28,380
Input abcdef, output 6, which is great.

276
00:14:28,380 --> 00:14:32,293
pwwekf-- I think this is right.

277
00:14:32,293 --> 00:14:33,960
TOMMY MACWILLIAM: Yep, that looks right.

278
00:14:33,960 --> 00:14:34,877
MARIA ZLATKOVA: --ekf.

279
00:14:34,877 --> 00:14:38,210
And then input empty string, output 0.

280
00:14:38,210 --> 00:14:39,390
Awesome.

281
00:14:39,390 --> 00:14:40,640
I think this looks good to me.

282
00:14:40,640 --> 00:14:43,820
Are there any other edge cases
that you want us to take a look at?

283
00:14:43,820 --> 00:14:45,260
TOMMY MACWILLIAM: No,
this looks great to me.

284
00:14:45,260 --> 00:14:47,260
And I think you might
have mentioned it already.

285
00:14:47,260 --> 00:14:49,440
But what's the runtime
of this final solution?

286
00:14:49,440 --> 00:14:50,273
MARIA ZLATKOVA: Yes.

287
00:14:50,273 --> 00:14:55,500
So space complexity is linear, since
we were using HashSet, and then

288
00:14:55,500 --> 00:14:57,870
time complexity.

289
00:14:57,870 --> 00:15:01,590
So we have one for loop,
which is linear time.

290
00:15:01,590 --> 00:15:07,720
And then searching within the HashSet
itself should be constant time.

291
00:15:07,720 --> 00:15:12,120
So I think it comes down
still to linear time.

292
00:15:12,120 --> 00:15:14,760
At most, we have to go through
each of the characters twice.

293
00:15:14,760 --> 00:15:16,847
TOMMY MACWILLIAM: Yeah,
that sounds right to me.

294
00:15:16,847 --> 00:15:17,430
Well, awesome.

295
00:15:17,430 --> 00:15:18,490
This looks great.

296
00:15:18,490 --> 00:15:21,200
Well, thanks so much for taking
the time to chat with me today.

297
00:15:21,200 --> 00:15:21,870
MARIA ZLATKOVA: Of course.

298
00:15:21,870 --> 00:15:22,728
Thanks so much too.

299
00:15:22,728 --> 00:15:24,270
It was a fun problem to work through.

300
00:15:24,270 --> 00:15:25,353
TOMMY MACWILLIAM: Awesome.

301
00:15:25,353 --> 00:15:26,630
Have a good one.

302
00:15:26,630 --> 00:15:28,000