Given a string, find the length of thelongest substringwithout repeating characters.Example 1:Input:"abcabcbb"Output:3Explanation:The answer is`"abc"`

, with the length of 3.

This is a typical sliding window problem and this post will introduce different approaches from the brute force one to the sliding window step by step, and you will see the time complexity could be improved from O(n^3) to O(n^2) and finally to O(n).

#### Brute force – O(n^3) & O(n^2)

We can used a nested for-loop to search each substring starting with each letter. Checking whether the next letter is existed requires O(n), adding up to O(n^3). Or, we can maintain a hashset containing all letters for the current substring, so that time complexity for examining the new letter could be reduced to O(1).

#### Sliding window – O(n) with two passes

To improve that, we can use sliding windows. Using `left`

and `right`

as two pointers to scan the input string. With the `hashset`

recoding the existing letters, once a repeated letter appears, we could move `left`

until the repeated letter was removed.

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
cur = set([])
left = right = 0
ret = 0
while left < len(s) and right < len(s):
if s[right] not in cur:
cur.add(s[right])
right += 1
ret = max(ret,right-left)
else:
cur.remove(s[left])
left += 1
return ret
```

#### Sliding window – O(n) with one pass

However, we can achieve it with one pass only. Based on the sliding window mentioned above, we can maintain another hashmap to record the position for each existing letters. In this case, instead of move `left`

letter by letter, we could jump to the next position of the repeated letter.

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
dic = {}
i = j = ret = 0
while j < len(s):
i = max(i,dic.get(s[j],-1)+1)
ret = max(ret,j-i+1)
dic[s[j]] = j
j += 1
return ret
```