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.
知识点
- 错误解法：这种解法得到的是从第一个非重复字符开始的最长字串。
# -*- coding: utf-8 -*-
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_length = 0
temp_length = 0
old_word = set()
# 对每一个字母
# 1 如果之前出现过， 则判断temp_length是否大于max_length，set.clear，temp_length = 1 ，加入到set中。
# 2 如果之前没出现过，则temp_length ++ ，加入到set中
# 退出循环后， 判断temp_length是否大于max_length
for i in s:
if i in old_word:
max_length = max(temp_length, max_length)
old_word.clear()
temp_length = 1
old_word.add(i)
else:
temp_length += 1
old_word.add(i)
max_length = max(temp_length, max_length)
return max_length
solution = Solution()
assert solution.lengthOfLongestSubstring("") == 0
assert solution.lengthOfLongestSubstring(" ") == 1
assert solution.lengthOfLongestSubstring("asc") == 3
assert solution.lengthOfLongestSubstring("aasc") == 3
assert solution.lengthOfLongestSubstring("bbbb") == 1
assert solution.lengthOfLongestSubstring("abcabcbb") == 3
assert solution.lengthOfLongestSubstring("dvdf") == 3 # 当出现重复字母时，clear时把需要的字串也去掉了
- 暴力方法，遍历所有子串，然后写个函数判断是否为不含重复字符子串，然后找最长的那个，复杂度为O(N^3)，会超时
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_length = 0
def check_unique(ss):
old_word = set()
for sss in ss:
if sss in old_word:
return False
old_word.add(sss)
return True
for i in range(0, len(s)):
temp_s = s[i:]
for j in range(0, len(temp_s) + 1):
sub_s = temp_s[:j]
if check_unique(sub_s):
max_length = max(max_length, len(sub_s))
return max_length
解题 1
- 分析一下暴力方法的缺点和优化：
- 每次判断字串是否为非重复，都需要遍历一遍字符串，复杂度为O(N)，但实际上如果字串中只多加了一个字符，这个新的字串只需要O(1)的复杂度就可以判断是否为非重复字串。
- 为了利用这个特点，我们使用
滑动窗口的方法遍历子串，对于字符串或者数组，用下标[i,j)表示窗口.[i,j+1)表示窗口向右扩大1，[i+1,j+1)表示窗口右移。 - 遍历方法为：
i从0到len(s)-1,j从i到len(s)-1，每次判断s[j]是否在set中，复杂度为O(n^2) - 同时注意到，如果
s[j]是否在set中，则以i为左窗口的字串最长长度就是j-i了，此时可以i++ - 最终答案为“以i为左窗口的最长子串”
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_length = 0
for i in range(0, len(s)):
set_start_from_i = set()
j = i
while j < len(s):
if s[j] in set_start_from_i:
break
else:
set_start_from_i.add(s[j])
j += 1
max_length = max(max_length, j - i)
return max_length
解题 2
- 同样的原因，在每次
s[j] in set,要更新i（右移左窗口）的时候，其实不需要把set清零。发现因为如果想把s[j]包含进来，必须不断左移i（set.pop(s[i]), i++），直到s[j] not in set。复杂度O(n)
- 算法总结如下：
- i，j代表左右窗，set代表窗中的内容，要求窗中内容没有重复的，求最大窗。
- 从0开始，j=i，先j向右扩张，
while(j<=len(s) and s[j] not in set):set.add(s[j]), j++。当结束的时候，说明要么到了最右端要么就不能再扩张了，此时长度j-i是以i为左端点时的最大窗口。 - 此时如果j==len(s)说明已经到最后了，可以结束，因为此时就是最长了。
- 之后找下一个i，while(i<len(s) and s[j] in set): set.pop(s[i]), i++
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
i = 0
j = 0
window_content = set()
max_len = 0
while i < len(s):
while j < len(s) and s[j] not in window_content:
window_content.add(s[j])
j += 1
max_len = max(max_len, (j - i))
if j == len(s):
break
else:
while i < len(s) and s[j] in window_content:
window_content.remove(s[i])
i += 1
return max_len
