3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

难度: Medium

刷题内容

原题连接

内容描述

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.

解题方案

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

求一个最长的子串,里面不带任何重复字符

假设input"abcabcbb"
我们先从第一个字符开始,只有一个字符肯定不会重复吧,“a”满足条件,更新最大长度为1
然后走到第二个字符,“ab”也满足,更新最大长度为2
走到第三个字符,“abc”也满足,更新最大长度为3
走到第四个字符,我们发现“a”已经出现过了,于是我们就必须要删除之前的一些字符来继续满足无重复字符的条件,但是我们不知道前面已经出现过一次的“a”index在哪里呀,所以我们只能一个一个找了,从当前子串的“abca”的第一个字符开始找,删除第一个字符“a”,发现这时候只剩下一个“a”了,我们又满足条件了,更新最大长度为3,以此类推

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: # 最新碰到的字符在当前子串中没有出现过
            lookup.add(s[end])   # 记录下当前子串新增的一个字符
            res = max(res, end-start+1) # 因为当前子串满足条件,更新最大长度
top Created with Sketch.