## # 3. Longest Substring Without Repeating Characters

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

Example 1:

``````Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
``````

Example 2:

``````Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
``````

Example 3:

``````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.
``````

### # Solution

Approach 1: Brute force.

Approach 2: Sliding window with a set by moving the head pointer one step a time.

Approach 3: Sliding window with a map by moving the head pointer bypassing the repeated element.

### # Code (Python)

Approach 2:

``````class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
result = 1
letters_in_window = set()
left = 0
for right in range(len(s)):
if s[right] not in letters_in_window:
else:
while s[left] != s[right]:
letters_in_window.remove(s[left])
left += 1
left += 1
result = max(result, right - left + 1)
return result
``````

Approach 3:

``````class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
result = 1
latest_positions = {s: 0}
left = 0
for right in range(1, len(s)):
if s[right] not in latest_positions or latest_positions[s[right]] < left:
latest_positions[s[right]] = right
else:
left = latest_positions[s[right]] + 1
latest_positions[s[right]] = right
result = max(result, right - left + 1)
return result
``````

### # Code (C++)

Approach 2:

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int tail = 0;
int maxLen = 0;
unordered_set<char> visited;
while (head < n && tail < n)
{
if (visited.find(s[tail]) != visited.end())
{
}
else
{
visited.insert(s[tail]);
tail++;
maxLen = (tail - head > maxLen) ? tail - head : maxLen;
}
}
return maxLen;
}
};
``````

Approach 3:

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int tail = 0;
int maxLen = 0;
unordered_map<char,int> visited;
while (head < n && tail < n)
{
if (visited.find(s[tail]) != visited.end() && visited[s[tail]] >= head) //!
{