# 3. Longest Substring Without Repeating Characters

## 1. Description

Given a string `s`

, find the length of the `longest substring`

without repeating characters.

Constraints:

- \(0 \leq s.length \leq 5 \times 10^{4}\)
`s`

consists of English letters, digits, symbols and spaces.

### 1.1. Examples:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. 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.

## 2. Solution

### 2.1. Understanding the problem

I think this is similar to two pointers where we maintain a `fast_pos`

and a `slow_pos`

.

The idea is that `fast_pos`

moves.

### 2.2. Algorithm

### 2.3. Code

def lengthOfLongestSubstring(s): """ :type s: str :rtype: int """ slow_pos = 0 fast_pos = 0 max_length = 0 while fast_pos < len(s): # we can still do one last comparison when fast_pos == len(s) - 1 substring = s[slow_pos : fast_pos + 1] if len(substring) == len(set(substring)): max_length = max_length if max_length > len(substring) else len(substring) else: # note we can't just move slow_pos to fast_pos here # as that will break test case "dvdf" slow_pos += 1 fast_pos += 1 return max_length # tests s = "" print(lengthOfLongestSubstring(s) == 0) s = "b" print(lengthOfLongestSubstring(s) == 1) s = "bba" print(lengthOfLongestSubstring(s) == 2) s = "pwwkew" print(lengthOfLongestSubstring(s) == 3) s = "dvdf" print(lengthOfLongestSubstring(s) == 3)

True True True True True

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(n)`

##### 2.3.1.2. Space complexity:

`O(n)`

, need the space for the substring.

### 2.4. Leetcode solution

`nil`

.

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

I reckon this is almost a two pointers question.

Also Leetcode provides an interesting optimized solution.