Longest Substring Without Repeating Characters
给你一个字符串 s。找出其中最长的不含重复字符的子字符串，也就是一段连续的字符，并返回它的长度。
大写字母和小写字母算作不同的字符，所以 a 和 A 不算重复。
函数
- sstring
- 要搜索的字符串
- 返回值integer
- 不含重复字符的最长子串的长度
约束条件
1 ≤ s.length ≤ 5 × 104s只包含英文字母（小写和大写）和数字。- 大写字母和小写字母是不同的字符。
示例
- 输入
- s = "coddycode"
- 输出
- 5
- 解释
ycode包含五个不同的字符。在它前面加上d后会得到dycode，其中d出现了两次，而且没有其他长度为五个或更长的连续字符不会重复。
- 输入
- s = "racecar"
- 输出
- 4
- 解释
race和ecar都包含四个不同的字母。每连续五个字母中都会有一个字母出现两次。
- 输入
- s = "a1b2a3b"
- 输出
- 5
- 解释
- 数字也算作字符，所以
1b2a3中有五个不同的字符。两个长度为 6 的连续段中，都各有第二个a或第二个b。
进阶
如果 s 可以包含任意 Unicode 字符，而不仅限于字母和数字，你会做哪些修改？
提示
逐个打开提示，每个都会多透露一点。
子字符串是字符串中连续的一部分，所以你要找的是一段最长的连续内容，其中没有重复字符。
保持一个有左边界和右边界的窗口。每次在右侧扩展一个字符，只有当新字符已经在窗口内时，才移动左边界。
记录每个字符上次出现的位置。如果新字符上次出现的位置在左边界处或之后，就将左边界移到该位置的后一位。左边界不会向左移动，答案就是你得到过的最宽窗口。
题解
维护一个窗口：用两个边界框住一段不含重复字符的连续片段。右边界每次读取一个字符，左边界只向前移动，因此遍历一遍就能找到每个结尾处最长的不含重复字符的连续片段。
检查每个子字符串
结果正确，但无法在最大的测试中运行完毕
思路
尝试每个起点和终点，将子字符串中的字符逐个加入集合进行测试，直到遇到已存在的字符。每个候选子字符串都会经过测试，因此不会漏掉最长的有效子字符串。
子字符串大约有 n²/2 个，当 n = 5 × 10^4 时为 1.25 × 10^9 个，而且一次测试最多可能读取 n 个字符：O(n³)。在这里，每次测试最多会在 63 个字符后停止，因为字符串中只有 62 种不同的字符，但测试次数仍然超过 10 亿次。
算法
- 将
best设为 0。 - 对于每个起始索引，从起始位置到字符串末尾遍历每个结束索引。
- 将子字符串中的字符逐个添加到一个空集合中，遇到第一个已在集合中的字符时停止。
- 如果没有重复字符，且子字符串长度大于
best，就保存它的长度。 - 返回
best。
def lengthOfLongestSubstring(s):
def has_no_repeat(start, end):
seen = set()
for k in range(start, end + 1):
if s[k] in seen:
return False
seen.add(s[k])
return True
best = 0
n = len(s)
for start in range(n):
for end in range(start, n):
if has_no_repeat(start, end):
best = max(best, end - start + 1)
return best
使用集合的滑动窗口
思路
如果 abc 没有重复字符，检查 abcd 只需问一个问题：d 是否在 a、b 和 c 中？用窗口中的字符组成一个集合，就能一次回答这个问题。
每次将 right 向右移动一步。如果新字符已经在集合中，就从左侧移除字符，直到它之前的副本被移除，然后将它加入集合并测量长度。只有在必须时才丢弃字符，因此对于每个 right，窗口都是以该位置结尾且不含重复字符的最长连续片段，而最佳子字符串会在某个位置结束。每个字符只会进入集合一次，离开集合最多一次：O(n)。
算法
- 从一个空集合开始，并设置
left = 0和best = 0。 - 让
right遍历每个索引。 - 当
s[right]在集合中时，移除s[left]，并将left向前移动一步。 - 将
s[right]添加到集合中。 - 如果
right - left + 1大于best，就保存它。 - 返回
best。
def lengthOfLongestSubstring(s):
in_window = set() # the characters between left and right
left = 0
best = 0
for right in range(len(s)):
# Shrink from the left until s[right] is no longer inside.
while s[right] in in_window:
in_window.remove(s[left])
left += 1
in_window.add(s[right])
best = max(best, right - left + 1)
return best
跳转到上次出现位置索引的滑动窗口
思路
你已经知道 left 应该移动到哪里：新字符上一次出现的位置之后一位。用映射或数组存储每个字符上一次出现的索引，数组中每个字符代码对应一个位置，这样 left 一步就能跳到那里。
只有当该索引大于或等于 left 时才跳转。更早出现的副本已经位于窗口之外，跳到那里会让 left 向后移动。每一步的窗口都与集合版本构建的窗口相同，而现在每个字符只需一次查找、一次比较和一次写入。
算法
- 创建一个空映射，用于记录字符及其最后出现的索引，并设置
left = 0和best = 0。 - 让
right遍历每个索引，读取该位置的字符ch。 - 如果
ch上次出现的位置大于或等于left，就将left设置为该索引加 1。 - 记录
right为ch最后出现的索引。 - 如果
right - left + 1大于best，就保存这个值。 - 返回
best。
def lengthOfLongestSubstring(s):
last_seen = {}
start = 0
best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
if i - start + 1 > best:
best = i - start + 1
return best
易错点和边界情况
- 向后移动
left。在abba中，到达最后一个a时，索引为 0 的前一个a已经在窗口之外。跳到索引 1 会让第二个b重新回到窗口中，结果是 3 而不是 2。 - 把窗口长度计算为
right - left。两端都在窗口内，所以要加 1。 - 先将字符串转换为小写。这里
a和A是不同的字符，所以aA的长度是 2。 - 只在出现重复字符时计算长度。像
z这样没有重复字符的字符串不会触发计算，结果会是 0。
常见问题3
无重复字符的最长子字符串的时间复杂度是多少？
滑动窗口的时间复杂度为 O(n)，其中 n 是字符串的长度：右边界会读取每个字符一次，左边界只会向前移动。额外空间复杂度为 O(k)，其中 k 是字符串可以包含的不同字符数，此处为 62。
存储最后出现的索引时，应该使用哈希表还是数组？
两者的时间复杂度都是 O(n)。像这里这样，字符集较小且固定时，使用字符编码作为索引的数组可以避免哈希运算，速度也更快。
子字符串和子序列有什么区别？
子字符串是相邻的一组字符，比如 coddycode 中的 ode。子序列可以跳过某些字符，比如 cdy。这道题要求找子字符串，所以使用有两个边界的窗口就可以了。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def lengthOfLongestSubstring(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "coddycode"
预期输出
5