## 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`

- If True: Resize the window to exclude the repeated character, i.e.
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
# Return answer
return ans
```