3. Longest Substring Without Repeating Characters

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

## 解题方案

- 时间复杂度: O(N)- 空间复杂度: O(N)

start
end
|
|
v

a  b  c  a  b  c  b  b

end 指针不停往前走，只要当前子串 s[start:end+1] 不满足无重复字符条件的时候，我们就让 start 指针往前走直到满足条件为止，每次满足条件我们都要update一下最大长度，即 res

slide window, beats 67.09%

python
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0

    start, end = 0, 0
res, lookup = 0, set()
while start < len(s) and end < len(s):
if s[end] not in lookup: # 最新碰到的字符在当前子串中没有出现过
res = max(res, end-start+1) # 因为当前子串满足条件，更新最大长度`