Skip to main content

Length of Longest Substring

Leetcode #3, "Medium": Longest Substring Without Repeating Characters

Here's a great solution I like. DataDaft channel is fantastic in general. https://www.youtube.com/watch?v=sUicrnHwA0s&ab_channel=DataDaft

# without comments...
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
sub = {}
longest = 0
cur_substr_start_index = 0
cur_len = 0

for i, letter in enumerate(s):
if letter in sub and sub[letter] >= cur_substr_start_index:
original_instanceOf_dupe_index = sub[letter]
cur_substr_start_index = original_instanceOf_dupe_index + 1
cur_len = i - original_instanceOf_dupe_index
sub[letter] = i
else:
sub[letter] = i
cur_len += 1
if cur_len > longest:
longest = cur_len
return(longest)
# With comments... May have messed up indents
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
sub = {}
longest = 0
cur_substr_start_index = 0
cur_len = 0

for i, letter in enumerate(s):
if letter in sub and sub[letter] >= cur_substr_start_index:
# store the index of the original duplicate for later comparison, i.e. this is the 2nd instance of c. the original is at sub[c], and so we keep sub[c] as the this original_instanceOf_dupe_index value.
original_instanceOf_dupe_index = sub[letter]
# Next we begin a new substr. The start is 1 letter over from the position of the original duplicate. Since we found a duplicate, we now need to begin a new substr, and we begin with the first letter after the original duplicate.
cur_substr_start_index = original_instanceOf_dupe_index + 1
# Since in this if statement, we have found a duplicate, we need to update the current length of the current substring we are on. It's the duplicate's index, minus the index of the original i.e. abcdefc ... well, we need the lenght of defc = 4. Index of orginal dupe would be 2, and the new dupe's index is 6. 6-2 = 4. This is our current substr length.
cur_len = i - original_instanceOf_dupe_index
# Now that we're done updating things, we overwrite the original dupe letter's index with the index of the new duplicate, so that we can re-calculate the next non-duplicate containing substr's length-- and if we find a new duplicate we will need to know the index of this "new original"-- i.e. this duplicate becomes the new original.
sub[letter] = i
else:
# We have not found a duplicate. So, we update our dictionary with our newest letter and its index
sub[letter] = i
# We update our cur_len to reflect that we're at a new non-duplicate letter
cur_len += 1
if cur_len > longest:
# now we check to see if our current substr's length is higher than the longest we've seen. If so, then we know we're currently on the longest and so we need to update the longest value to be our current substr length.
longest = cur_len
# Once our loop ends and we have iterated over everything, we return the value of longest which will contain the value of the length of the longest substr.
return(longest)