TOMMY MACWILLIAM: So what we're going to do is, given a string,
we're going to be looking for the length of the longest substring
without repeating characters.
So, for instance, if I gave you the string abcabcbb, the length
of the longest substring there is 3.
So there's abc, where it doesn't have any repeating characters in there.
And there's a few other ones like that.
So your function would take that as input
and then just return the length of that string, which is 3.
MARIA ZLATKOVA: Awesome.
Hey, Tommy.
How are you?
TOMMY MACWILLIAM: Awesome.
How's it going?
MARIA ZLATKOVA: Good.
How's your day going?
TOMMY MACWILLIAM: I'm good.
It's a sunny day still in San Francisco.
So I'm loving it.
MARIA ZLATKOVA: Beautiful.
It's kind of a gloomy day in New York but still pretty warm.
So I'll take it.
TOMMY MACWILLIAM: Nice.
Well, thanks so much for jumping on the call.
Let's jump into a coding problem.
MARIA ZLATKOVA: Awesome.
TOMMY MACWILLIAM: All right.
So it looks like you've got the Replit set up.
Notice you're set to Python.
Is that the language you'd like to use?
MARIA ZLATKOVA: Yep, that's the language I'd like to use,
if that sounds good with you.
TOMMY MACWILLIAM: Perfect.
That's good with me.
MARIA ZLATKOVA: Cool.
Just thinking through this question a little bit,
I guess a few clarifying questions.
So we just want to find the length, right?
We don't care about returning one or all of the subsequences
that match that length.
TOMMY MACWILLIAM: Yep, that's right.
MARIA ZLATKOVA: Awesome, cool.
And then when it comes to the input, I see
the example we have here is all lowercase characters.
Should we assume that we're going to get all lowercase characters as input?
Or do we want to handle sanitizing that input?
TOMMY MACWILLIAM: That's a good question.
You can assume the input's all lowercase.
MARIA ZLATKOVA: Awesome, cool.
And I guess could then put be empty, like the empty string.
TOMMY MACWILLIAM: It could, in which case you return 0.
MARIA ZLATKOVA: Awesome, cool.
Great.
I think that covered all of my questions.
So maybe then just give a few examples.
So abcabcbb, the answer would be 3, the output that we want to give.
If we have all repeating characters, the output would be just 1, I'm assuming?
TOMMY MACWILLIAM: Yep, that's right.
MARIA ZLATKOVA: Awesome.
And conversely, if we have all different characters,
the output would be 6 in this case.
TOMMY MACWILLIAM: Yep.
MARIA ZLATKOVA: And then, as we said, if we get the empty string,
the output would be 0.
Yeah, awesome.
I think that makes a lot of sense to--
when I'm looking at this initial string and problem,
I guess the first instinct that I have for the very naive solution
is that brute force, we can just get all of the possible subsequences
or substrings and check whether there are any duplicate characters
within those substrings.
So in the abcabcbb example, that would be first starting with every substring
starting with a would be a and checking if that has any repeating characters.
Then ab-- it doesn't have any duplicate characters.
Then abc-- it also doesn't have any duplicate characters.
Then abca, which has duplicate characters.
And then every single one-- abcab would also
have duplicate characters, given that the substring of that had them
and also that b is repeating, similar with abcabc, abcabcb, and abcabcbb.
So it would be a very similar case if we start at b and at c.
So it's making me feel like the naive solution,
we'd be doing a little bit of work that is not useful.
So if we could avoid that, that would be great.
Reasoning a little bit over that naive solution brute force approach,
going through all possible subsequences would be quadratic time.
And then within that, checking whether there are duplicate characters
within each substring would be linear time.
So in total, that probably would be n to the third.
So that is not great.
So I'm going to try to optimize that if we can.
And looking at this, the way I described it,
starting at different points of the string,
I'm starting to think maybe we can have a range within the string
that we track with a starting index and an ending index.
And maybe we can expand--
the start of string and expand our ending index to the right.
And the moment we encounter a duplicate character or a repeating character,
we start to move our start index forward to try
to get to a subsequence that doesn't contain
that duplicate character anymore.
And all the while, while we're doing that,
keep track of the longest encountered length.
And I guess I have-- another assumption question is,
could we use an extra data structure in this question?
TOMMY MACWILLIAM: Yeah, that's totally fine.
I think that that sliding window you're describing,
that sounds like a pretty good approach to me.
MARIA ZLATKOVA: Awesome.
Yeah, I think for that sliding window, I'd
like to use a HashSet so that we can have pretty constant time in looking up
how often certain characters are within the string already.
And we can do that lookup very quickly.
TOMMY MACWILLIAM: Yeah, that sounds great.
MARIA ZLATKOVA: Awesome.
So if that sounds good, I'm going to go ahead and define our function.
I'm going to call it length of longest substring.
We take in just one parameter, I'm assuming, which is the string.
TOMMY MACWILLIAM: Yep.
MARIA ZLATKOVA: And then I need to define the output, which is an integer.
Cool.
So as I said, would love to use a HashSet.
So I'm just going to start by initializing it.
And can just initialize it all to 0's for now and count--
we're going to count how many occurrences of each character that we
encounter happen within the substring.
And I'm going to multiply that by 128, because I
know that we have 128 ASCII characters.
So just to start off, initialize it to that.
And then going to define the length, which
we're going to want to track of that longest substring,
and define that to 0.
Getting some-- ah.
Oh, OK.
Variable assigned but never used.
That's OK, because we haven't used it yet.
And then going to use the start and end index
approach that I described with that sliding window.
So the start index--
maybe I'll just call it left for clarity.
I'm going to assign that to 0.
And then what we want to do first is start going through the string.
We can do it in a few ways.
A while loop-- but maybe I'll do a for loop to start.
So can say for right--
and right is referring to my end index, which I described-- for right in range
of the length of the string.
Thankfully, saw Connor's previous interview,
so I now know that we can [INAUDIBLE] here.
But we have to do the length of the string.
And then the first thing I want to do in this case is to make sure that--
basically, what we want to do is increment
the count of the specific character that we're at by 1 in the HashSet
that we have.
So the way we're going to do that is we're going to say chars at s
at index right, because s is our string.
And we're going to increment that by 1.
And that's OK because we've defined all of the characters--
all of the essentially fields and our HashSet to be 0.
Cool.
So then the next thing I want to do is I want to take care of that case
which I mentioned earlier, which is if we encounter a duplicate character,
it's moving the left or the start index forward until we don't
have a duplicate character anymore.
And since we're using chars as our HashSet,
the way that we know that we've encountered more than one character
is if chars at s index right is greater than 1.
And so I'm going to do a while loop here because we
could have multiple repeating characters within the substring.
So I want to make sure that I get rid of all potential repeating characters.
Or the repeating character could actually
be at a later point in the substring.
So I want to get to that point and make sure I move the start
index by enough characters forward.
So the way we're going to do this is first we
want to update the count that we're keeping
track of in our HashSet for that specific character.
So the way we're going to do that is we're going to say chars at s at--
I think I called it left--
[INAUDIBLE] minus equals 1.
And then what I'm going to do is-- to move left forward--
is I'm just going to increment left.
Cool.
And then one thing which I haven't done yet
is I want to make sure I'm keeping track of the length, as we said earlier.
So the length at the first iteration will be--
we've initialized it to 0.
And then-- the first time we calculated.
The length between two indexes in a string
typically is the ending index minus the starting index plus 1,
because strings are 0 index.
So in our case, it's right minus left plus 1.
If I could spell correctly, that would be great.
And then what I'm going to do so that we always keep track of the biggest--
the maximum possible length is I'm going to use the max function
and say I want to take the max of either the current length or--
the length that we've been keeping track of or the current length based
on the right and left integers.
And then the last thing we want to do is return the length,
because we want to return that integer.
Cool.
And I guess, just to sanity check a little bit
before I run this, just going to do it with abca,
because it's a little bit shorter than abcabcbb.
So abca should be 3, the output for that.
So what we're going to do is when we start our for loop,
we're going to say that chars at a is equal to 1.
We're going to add 1 to that.
It's not greater than 1 in the first iteration.
So what we're going to do is just take the length and set it.
And because right and left are 0 at that first run through the for loop,
it's going to be 0 minus 0 plus 1.
So length is going to be 1 at this stage.
And then when we get to b, chars at b is going to be granted to 1.
Chars at b still is not greater than 1.
So again, we're just going to jump with length.
And at this point, it's going to be 2, because 1 minus 0 plus 1 is 2.
Then we're at index 2, which is a third character, which is c.
So again, setting chars at c to be 1.
And then it's not greater than 1.
So we just jump and then increment the length again to 3 this time,
because 2 minus 0 plus 1 is 3.
And then in the final run-through of that for loop,
we're going to encounter a again.
And so chars at a is now equal to 2, which is greater than 1.
So what we're going to do is decrement that.
So again, chars at a becomes 1.
And we're going to move it forward--
left, sorry-- our left index forward.
And what we get now is that we want to take the max of either 3 or 0, 1, 2, 3.
So 1, 2, 3, which again is going to give us length 3.
And we've run through basically all of the elements here.
So what we're going to do is just return line three.
So just by running through this simple example, I think this should work.
And I'm going to write out some test pieces.
So maybe I'll just print input and maybe just define our string here.
The first will be abcabcbb.
Our input is going to be string.
And then we want to say length is equal to calling the function on string.
And finally, print output to be length.
Cool.
So it may have some errors.
I'm just going to run it through the first time and see what happens.
And I see here that on line 14, we have "lists indices must
be integers or slices, not strings."
So looking at line 14--
oh, I think this is very interesting, because I referred to ASCII characters
in the beginning, but then I didn't really
take into account that we can't have a character itself as the index.
But we have to--
I think we have to use a function called ord.
TOMMY MACWILLIAM MACWILLIAM: Yep, that's right.
MARIA ZLATKOVA: Awesome.
Yeah, I think that function returns an integer that
represents the Unicode character.
So what I want to do is I want to wrap ord around every single time I'm
using an index within chars.
Those should be all the times.
And then input abcabcbb, output 3.
That's great.
I'm just going to run through and add a few more test
cases like the ones we mentioned.
So bbb, abcdef.
Oh.
And maybe just add the empty string for good measure
to see if that gets us the right result.
Cool.
So we get input bbb, output 1, which is great.
Input abcdef, output 6, which is great.
pwwekf-- I think this is right.
TOMMY MACWILLIAM: Yep, that looks right.
MARIA ZLATKOVA: --ekf.
And then input empty string, output 0.
Awesome.
I think this looks good to me.
Are there any other edge cases that you want us to take a look at?
TOMMY MACWILLIAM: No, this looks great to me.
And I think you might have mentioned it already.
But what's the runtime of this final solution?
MARIA ZLATKOVA: Yes.
So space complexity is linear, since we were using HashSet, and then
time complexity.
So we have one for loop, which is linear time.
And then searching within the HashSet itself should be constant time.
So I think it comes down still to linear time.
At most, we have to go through each of the characters twice.
TOMMY MACWILLIAM: Yeah, that sounds right to me.
Well, awesome.
This looks great.
Well, thanks so much for taking the time to chat with me today.
MARIA ZLATKOVA: Of course.
Thanks so much too.
It was a fun problem to work through.
TOMMY MACWILLIAM: Awesome.
Have a good one.