Leetcode - Longest Substring Without Repeating Characters

Question

Given a string s, find the length of the longest substring without repeating characters.

This is asliding_window question.

Idea

• Define a set for O(1) look up
• Iterate through the string (while R < len(s))
• If current char is not in set, add to set and increment R
• Otherwise, set res to the max of itself and the length of the set, remove left pointer from set, increment L (the idea here is the shorten the window (increment L) until the char at the right pointer is no longer in the window so we can keep moving the window forward)
• Since we only update the result on finding a duplicate, after the loop we need to see if we ended the loop without finding a duplicate, so set res to the max of itself and the length of the set
• Return res

Solution