# 3. Longest Substring Without Repeating Characters 无重复字符的最长子串

@TOC

## # 题目描述

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

Example 1:

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

## # 解题方法

### # 解法一：虫取法+set

a b c b b c b b 0 1 2 3 4 5 6 7

``````class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
left, right = 0, 0
chars = set()
res = 0
while left < len(s) and right < len(s):
if s[right] in chars:
if s[left] in chars:
chars.remove(s[left])
left += 1
else:
right += 1
res = max(res, len(chars))
return res
``````

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int N = s.size();
if (N <= 1) return N;
unordered_set<char> set;
int res = 0;
int l = 0, r = 0;
while (r < N) {
while (set.count(s[r])) {
set.erase(s[l]);
++l;
}
set.insert(s[r]);
res = max(res, int(set.size()));
++r;
}
return res;
}
};
``````

### # 方法二：一次遍历+字典

left一定是向右移动的，不可能撤回到已经移动过的位置。

``````class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
left, right = 0, 0
res = 0
chars = dict()
for right in range(len(s)):
if s[right] in chars:
left = max(left, chars[s[right]] + 1)
chars[s[right]] = right
res = max(res, right - left + 1)
return res
``````

C++代码如下，注意C++的变量务必需要初始化，否则将不确定，比如这里的l和res，如果不初始化会产生莫名其妙的结果：

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int N = s.size();
unordered_map<char, int> pos;
int l = 0;
int res = 0;
for (int r = 0; r < N; ++r) {
if (pos.count(s[r])) {
l = max(l, pos[s[r]] + 1);
}
pos[s[r]] = r;
res = max(res, r - l + 1);
}
return res;
}
};
``````

## # 日期

2018 年 8 月 24 日 —— Keep fighting! 2019 年 1 月 19 日 —— 有好几天没有更新文章了