# Longest Substring Without Repeating Characters

I’m trying to get in a habit of starting my mornings off with coffee and a Leetcode problem before work. Ease my way into the day and get the brain juices flowing. Let’s jump in!

## Longest Substring Without Repeating Characters

### Problem

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

Example inputs:

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

### Thinking

I spent some time thinking about this but couldn’t come up with anything faster than `O(N^2)`

although I can almost guarantee there is a way.

In any case, the thought is iterate through the permutations and use a set to track the characters seen. When we run into a character we’ve seen, capture the length (if the max), and reset on next initial character.

### Corner Cases

The following corner cases are what I missed in my initial solution:

- If iteration completes w/o running into a character it hasn’t seen.

### Improvements

There is probably a way to cleanup the logic so the seen & fallthrough code can be merged instead of copied.

There is probably a faster solution than `O(N^2)`

.

### Solution

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
seen = set()
max_len = -1
for i in range(0, len(s)):
seen.add(s[i])
for j in range(i+1 , len(s)):
if s[j] in seen:
max_len = max(max_len, len(seen))
seen.clear()
break
else:
seen.add(s[j])
else:
max_len = max(max_len, len(seen))
seen.clear()
return max_len
```

### Score

```
Runtime: 508 ms, faster than 15.12% of Python3 online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 13.9 MB, less than 5.10% of Python3 online submissions for Longest Substring Without Repeating Characters.
```