## Problem

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

Example 1:

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

Example 2:

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

Example 3:

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

## Thought Process

- Brute force, nested loop to loop thru all the sub-strings
- use a list to store sub-string; and a dict whose key is the len of substring, and value is the substring
- return max len substring

## White Board

The brute force solution has some issues. But I thought about using shifting window to solve it

## Code

```
class Solution:
def lswp(self, my_str):
res = {}
for i in range(len(my_str)):
temp = []
temp.append(my_str[i])
for j in range(len(my_str)):
if my_str[j] not in temp:
temp.append(my_str[j])
else:
break
res[len(temp)] = "".join(temp)
return(max(res))
def test_lswp():
lswp = Solution().lswp("abcabcbb")
print(lswp)
test_lswp()
```

```
3
```

I think this brute force solution is not correct

## Complexity

- Time complexity is O(n**2), two nested loops
- Space complexity is O(n), as I did create additional dictionary and list to store the results

## Optimization

Use shifting-windows, and an ascii array to check if a char exists in the current sub-string

```
class Solution2:
def lswp2(self, s):
freq = [0] * 128
# use freq to store the freq of all the chars
l, r = 0, -1
# shifting window is s[l,r], with invalid init state
res = 0
# initially res is 0
while l < len(s):
# as long as l can still move to the right
if((r + 1 < len(s)) and (freq[ord(s[r+1])] == 0)):
# r can still move to the end
r += 1
freq[ord(s[r])] += 1
else:
# if s[r+1] already exists, a.k.k freq[ord(s[r+1])] = 1
# move l until s[r+1] doesn't exist in s[l, r]
# every l += 1, need to exclude s[l] first, so s[l] is not in s[l,r] no more
freq[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)
if res == 0:
return 0
return res
def test_lswp2():
lswp2 = Solution2().lswp2("xxzqi")
print(lswp2)
test_lswp2()
```

```
4
```

Now the time complexity is O(n), space complexity is O(128) => O(1) since I use a space of 128 to store all ascii value