Coding Interview Tutorial 24: Longest Substring without Repeating Characters [LeetCode]

Learn how to find the length of the longest substring without repeating characters in O(N) time, where N is the length of the input string.

This is an important programming interview question, and we use the LeetCode platform to solve this problem.

[divakarbogapurapu]

Thanks a lot for your explanation Amell!

[TeluguAbbi]

Great explanation, Amell! The problem couldn't have been easier than the way you solved it.

[mohammadyahya]

Thank you very much! I was confused first as we deleted elements from hash set without knowing what we delete. Then I realized the point is not that we track which character to remove from hash set but we track the longest window! Please correct me if I am wrong?

[danavram]

An important point is that the HashSet data structure is what makes this algorithm work. Otherwise, you'd need to increase the complexity by checking duplicates on the right side and removing the chars from before. As a further note, in Python, the Set is based on hash tables and has a lookup time of O(1) (if there are no collisions, ofc). Therefore, the Hash Set in Java and the Python Set provide the underlying functionality to get this working in O(n).

uniqueChars = set([])
counter = 0
for c in s:
if c not in uniqueChars:
uniqueChars.add(c)
else:
uniqueChars.pop() # remove first
counter = max(counter, len(uniqueChars))
counter = max(counter, len(uniqueChars))
return counter


There is a way to still keep the time complexity of O(n), by using a hash table and a list (but of course, this increases space complexity).

[nithishreddy]

please make such videos it help me a lot

[bhaskarmahajan]

I don't get the concept of increasing the left
Suppose the string was "xabcabcbb "
After reaching the first repeating character (here 'a') and incrementing left, the sub-string will still be holding two a's (abca)

[shwetanksingh]

Hi, Shouldn't the time complexity be O(n log n) since it takes log n time to search ( in CPP ) for characters and what would be the space complexity in this case?

[mcreyfonacier]

is it fine not to use .contains method and create my own method instead for a faster running time? thanks

[saviopereira]

This code would not work for the input "abcdefcghif".


I believe you need another while loop in the if condition that checks if the value is present in the set