Longest Substring without Repeating Characters

• LeetCode

• Two pointers, r and l, both at 0.
• Set which keeps track of characters already seen.
• Increment r, add to set.
  • Before adding char at r to set, check if char at l is in set. While char at l is in set, keeping popping the character at l.
  • This is because our substring can't have repeating characters.

Instead of iterating one by one till our substring doesn't have empty characters, we can keep track of the indexes so that once a duplicate is seen, we can immediately jump to the new index.

There is an extra condition:

• If we see a duplicating character, we cannot immediately move the index to the next of the one already seen.
• This is why: Basically l can't move left. It can only move right. So either move it right or leave it unchanged. You only move it right when l is less than the current repetition. If l has somehow moved ahead then there's no need to move it left. For example in abba. When the second a is encountered, l has moved ahead from first a and is on the second b. But the map still remembers that as the last seen a. Now just to eliminate the left a if we move l by just 1 then it will land on first b. l moved backwards. Before it was on second b and now it is on first b. Just don't update it in this case. Just update the repeated character position in the map and now back to normal, l has become less than the next repeating a, so now l can move, if it sees another a.
• If l is not lesser than the index of the repeating character, the next line chars_seen[s[r]] = r will make sure that l is updated in the next iteration. It doesn't matter that the next line longest_len = max(longest_len, r - l + 1) runs, because our sliding window would've gotten smaller. So it's redundant if it runs.