> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/sliding-window]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/longest-substring-without-repeating-characters/]
> [up:: [[Leetcode MOC]]]
## Problem
Given a string `s`, find the length of the **longest substring** without repeating characters.
**Example 1:**
**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.
**Example 2:**
**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.
**Example 3:**
**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.
**Constraints:**
- `0 <= s.length <= 5 * 104`
- `s` consists of English letters, digits, symbols and spaces.
## Solution
### Mine
#### Python
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
longest_substring = 0
local_substring = 1
seen = set()
i = 0
j = 1
if len(s) <= 1:
return len(s)
while j < len(s):
seen.add(s[i])
if s[i] == s[j] or s[j] in seen:
longest_substring = max(longest_substring, local_substring)
seen.remove(s[i])
i += 1
local_substring = j - i + 1
else:
seen.add(s[j])
local_substring = j - i + 1
j += 1
if i == j:
j += 1
longest_substring = max(longest_substring, local_substring)
return longest_substring
```
#### Rust
### Neetcode's
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l += 1
charSet.add(s[r])
res = max(res, r - l + 1)
return res
```
## Things I Learned
### Neetcode Video
A key thing to remember is that if you hit a duplicate, you have to update the left pointer to the first duplicate's index + 1. You can't just increment by 1 and be done. However, my solution takes care of this because the first check is `if len(s) <= 1`.
The time complexity is $O(n)$ and memory complexity is also $O(n)$ thanks to the set.
## Scratchpad
Start with an a pointer $i$ at position 0 and one $j$ at 1. If the values aren't equal, add to local length and increment $j$. If they are, get max of overall length and current length, then increment $i$ and repeat.
I got mostly there but kept getting hit with edge cases.