# 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:
letters_in_window.add(s[right])
else:
while s[left] != s[right]:
letters_in_window.remove(s[left])
left += 1
left += 1
letters_in_window.add(s[right])
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]: 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 head = 0;
int tail = 0;
int maxLen = 0;
unordered_set<char> visited;
while (head < n && tail < n)
{
if (visited.find(s[tail]) != visited.end())
{
visited.erase(s[head]);
head++;
}
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 head = 0;
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) //!
{
head = visited[s[tail]] + 1;
}
visited[s[tail]] = tail;
tail++;
if (tail - head > maxLen)
maxLen = tail - head;
}
return maxLen;
}
};