Medium Hash Set Window Sliding Window
In plain English: Find the longest stretch of characters in a string where no character appears twice.
Expand the window right, adding chars to a set. When a duplicate is found, shrink from the left until the duplicate is removed. The set guarantees O(1) membership checks.
Prompt
Given a string s, find the length of the longest substring without repeating characters.
Try to write it from scratch before scrolling down.
Solution
def length_of_longest_substring(s):
char_set = set()
l = 0
max_len = 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l]) # shrink from left
l += 1
char_set.add(s[r])
max_len = max(max_len, r - l + 1)
return max_len
# Test: length_of_longest_substring("abcabcbb") == 3 ("abc")
# Test: length_of_longest_substring("bbbbb") == 1