# Longest Substring Without Repeating Characters

## # Solution

Let

### # Brute Force

The brute force solution is not shown.

Complexity:

- time:
- a nested for loop for the sliding window and to check if unique takes
time

- a nested for loop for the sliding window and to check if unique takes
- space:
space for the sliding window, where is the size of the Set, which is upper bounded by and

### # Sliding Window Using HashSet

The idea is to use a sliding window to locate a substring, and a HashSet `st`

to see if the new char is already seen previously.

Sliding window logic: `i`

is the left boundary and `j`

the right boundary. Increase `j`

by 1 if `s[j]`

has not occurred in the current subarray. Increase `i`

if `s[j]`

has occurred.

Invariant: `i`

<=`j`

Complexity:

- time:
- worst case
: all characters are the same and each will be visited by both and

- worst case
- space:

```
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
n = len(s)
st = set()
i = j = 0
res = 1
while i<n and j<n:
if s[j] not in st:
st.add(s[j])
j += 1
res = max(res, j-i)
else:
st.remove(s[i])
i += 1
return res
```

### # Sliding Window Using HashMap

If having seen the new char in existing window, could update the left boundary to `d[val]+1`

(

Several optimizations:

`start`

and`idx`

rather than`i`

and`j`

to refer to left and right boundaries of window`enumerate`

`idx`

and`val`

`dct`

to store the mapping from`val`

to`idx`

Complexity:

- time:
- space:

```
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
start = 0
dct = {}
for idx, val in enumerate(s):
if s[idx] in dct:
start = max(start, dct[val]+1)
res = max(res, idx-start+1)
dct[val] = idx
return res
```