## Problem Statement#

### Description#

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

### Examples#

#### Example 1:#

``````Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
``````

#### Example 2:#

``````Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
``````

#### Example 3:#

``````Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring,
"pwke" is a subsequence and not a substring.
``````

### Constraints#

• `0 <= s.length <= 5 * 104`
• `s` consists of English letters, digits, symbols and spaces.

## Key Insights#

• To solve this problem in O(N) time, we can design a Sliding Window algorithm that uses a Hash Map data structure. The Sliding Window will use left `l` and right `r` pointers to define the window and a Hash Map `mp` to keep track of the indexes of each unique character in the window. (Note: `mp` contains the indexes of all previously seen characters–even if they don’t appear in the window. There’s no need to purge these.)

• For each iteration of `r`, check if the current character `ch` appears in `mp`. If it does, further check if the left `l` pointer is at or before the index of `ch` i.e `l <= mp[ch]`.

• If True: Resize the window to exclude the repeated character, i.e. `l = mp[ch] + 1`.
• Otherwise: Update the length of the longest unique substring `ans = max(ans, r - l + 1`
• Finally, update the “index of the last occurrence of `ch`”, i.e. `mp[ch] = r`. Since this statement is the last thing that happens in the loop, it becomes historical information for the next iteration.

## Python Solution#

### Optimized Sliding Window#

``````
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
0   1   2   3   4   5   6   7
a   b   c   a   b   c   b   b
^r
^l

Time:   O(n)
Space:  O(min(n, m)) | m=size of charset
"""
l = 0
n = len(s)
ans = 0
mp = {}

# Right pointer (r) slides across whole range
for r in range(n):

# We will use the current character (ch) multiple times
ch = s[r]

# Resize window to exclude previous occurrence of (ch)
if ch in mp and l <= mp[ch]:
l = mp[ch] + 1

# Update window size (ans) if (ch) appears once in the window
else:
ans = max(ans, r - l + 1)

# Add "previous occurrence" of (ch) to hashmap (mp)
mp[ch] = r