# 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)):

for j in range(i+1 , len(s)):
if s[j] in seen:
max_len = max(max_len, len(seen))
seen.clear()
break
else:
``````Runtime: 508 ms, faster than 15.12% of Python3 online submissions for Longest Substring Without Repeating Characters.