无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度, "pwke"是一个子序列，不是子串。
首次提交
想法
- 第一层循环遍历字符长度
- 从最长到短以节省时间
for i in range(len(s),-1,-1)
- 第二层循环滑动截取子串的窗口
for j in range(len(s)-i+1)表示子串第一个字符的索引, “+1”是因为当len(s)等于i，也就是最长的子串时，第一个字符的索引为0，仍然可以判断。- 截取子串为
targer = s[j:i+j]
- 对于截取到的子串判断是否有重复字符
- 对于截取到的子串，排序后检查每个字符是否等于下一个字符，如果通过则说明没有重复字符
- 没有重复就是最长子串，有重复跳过
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
length = len(s)
if length == 0:
return 0
for i in range(length,0,-1):
for j in range(length - i + 1):
target = sorted(s[j:j+i])
for k in range(i-1):
if target[k] == target[k+1]:
break
else:
return i问题
超出时间限制
复杂度
最坏情况下总时间复杂度大约为 O(n³ log n): 生成子字符串： O(n²)，排序子字符串: O(n log n)
新方法
使用两个指针，左指针从左往右每个字符依次开始，维护一个判断是否重复的set，右指针从当前字符到s的结尾一个一个判断，如果当前右指针指向的字符位于set中，则记录下左指针到右指针的距离+1并与最大子串长度判断，大于则更新最大子串长度。从左指针指向的下一个字符再次开始知道左指针指向最后一个字符。
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
max_length = 0 # 最大子串长度
n = len(s)
# 外层循环，左指针从头开始
for left in range(n):
seen = set() # 用来存储当前窗口中的字符
for right in range(left, n): # 右指针从当前左指针开始
if s[right] in seen: # 如果遇到重复字符，记录最大长度
break
seen.add(s[right])
max_length = max(max_length, right - left + 1) # 更新最大长度
return max_length复杂度
这个实现的时间复杂度为 O(n²)，其中 n 是字符串的长度。每次左指针向右移动时，右指针需要扫描剩余的字符，虽然有set来检查重复字符，但每次插入和删除操作的时间复杂度是常数时间，因此整体时间复杂度为 O(n²)。
最终方法
优化思路
- 滑动窗口:
- 使用两个指针，
left和right，并维护一个滑动窗口。 right负责扩大窗口，left在遇到重复字符时负责收缩窗口，直到去除重复字符。
- 使用两个指针，
- 哈希集合:
- 使用一个集合
seen来记录当前窗口中的字符。 - 每次遇到重复字符时，移动
left指针到重复字符的下一个位置。
- 使用一个集合
- 时间复杂度:
- 由于每个字符至多会被
left和right指针遍历一次，所以整体时间复杂度为 O(n)，这是最优解法。
- 由于每个字符至多会被
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set() # 用集合记录当前窗口中的字符
left = 0 # 左指针
max_length = 0 # 最大子串长度
for right in range(len(s)): # 右指针
# 如果窗口内已经包含右指针指向的字符s[right]，
# 那么再加入一个 s[right] 会导致窗口内有重复元素
# 所以要在加入 s[right] 之前，先移出窗口内的 s[right]
while s[right] in seen: # 如果右指针指向的字符已存在于集合中
seen.remove(s[left]) # 移除左指针指向的字符
left += 1 # 将左指针向右移动
seen.add(s[right]) # 将当前字符加入集合
max_length = max(max_length, right - left + 1) # 更新最大长度
return max_length
复杂度分析
时间复杂度：O(n)，其中 n 为 s 的长度。注意 left 至多增加 n 次，所以整个二重循环至多循环 O(n) 次。
空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128。
|´・ω・)ノ