Longest Substring Without Repeating Characters - LeetCode #3 with LEGO
Hello everyone! This video walks through a sliding window algorithm to solve the problem of finding the longest substring without repeating characters.
This algorithm runs in O(n) time, as i iterates over each character once.
The algorithm's dictionary uses O(min(m, n)) space, where m is the size of the character set (so 26 for lowercase English characters). This is due to the last index of each character getting overwritten when seen more than once.
I recommend pausing the video to see what the code is doing at certain points, and don't hesitate to ask questions! I went a little out of order regarding the actual steps when walking through with the LEGO bricks, but I hope I conveyed the general idea behind the algorithm well enough for you to grok it.