LeetCode | 无重复字符的最长子串

题目#

给定一个字符串 s，找出其中不含重复字符的最长子串长度。

这里的子串必须是连续的一段。

示例：

1
输入：s = "abcabcbb"
2
输出：3
3
原因：答案可以是 "abc"，长度为 3。"bca" 和 "cab" 也可以。

1
输入：s = "bbbbb"
2
输出：1
3
原因：答案是 "b"，长度为 1。

1
输入：s = "pwwkew"
2
输出：3
3
原因：答案是 "wke"，长度为 3。"pwke" 不是子串，因为它不是连续的一段。

讲解#

这道题要找的是“没有重复字符”的最长连续片段。

遇到下面几种信号时，经常可以考虑滑动窗口：

• 题目要求的是连续的一段，比如子串、子数组
• 需要找最长、最短、最多这类范围问题
• 右边界可以一步步往右扩
• 如果窗口不满足条件，左边界可以一步步往右缩

这道题正好符合这些信号：子串必须连续，目标是找最长；没有重复时可以继续往右扩，出现重复时就从左边缩小窗口。

做法是滑动窗口。窗口可以理解成字符串里当前正在看的连续片段。

我们维护一个窗口 [left, right]，并保证窗口里没有重复字符。right 从左到右扫描字符串，left 只在遇到重复字符时往右移动。

curr 是一个集合，用来记录当前窗口里有哪些字符。

当新字符 ch 已经在 curr 里时，说明窗口里已经有一个同样的字符了。这个重复字符不一定就在最左边，所以不能假设 s[left] 一定是它。

代码的做法是：从窗口最左边开始删，一个一个删，直到窗口里不再有 ch。

1
while ch in curr:
2
    curr.remove(s[left])
3
    left += 1

注意这里用的是 while。意思是：只要新字符 ch 还在窗口里，就继续缩小窗口。

以 s = "abcabcbb" 为例。当 right 走到第二个 a 时：

1
当前窗口: "abc"
2
curr = {a, b, c}
3
新字符 ch = "a"

此时 "a" 已经在窗口里。刚好最左边也是 "a"，删掉它以后窗口变成 "bc"，就可以把新的 "a" 加进来，窗口变成 "bca"。

但重复字符不总是在最左边。看 s = "abba"：

1
窗口先变成 "ab"
2
接下来遇到第二个 "b"

这时重复的是 "b"，但窗口最左边是 "a"。所以第一步先删 "a"，窗口变成 "b"；可是 "b" 还在窗口里，所以还要继续删 "b"。删到窗口里没有 "b" 以后，才能把新的 "b" 加进来。

所以这段代码不是因为“最左边一定是重复字符”才删最左边，而是因为窗口要保持连续。想让左边界右移，只能从最左边开始一个个移除，直到重复字符被移出窗口。

这个方法快的原因是：left 和 right 都只会从左往右走，不会回头。

复杂度：

• 滑动窗口：时间复杂度 O(n)，空间复杂度 O(n)

代码#

1
class Solution:
2
    def lengthOfLongestSubstring(self, s: str) -> int:
3
        curr = set()
4
        left = 0
5
        ans = 0
6

7
        for right,ch in enumerate(s):
8
            while ch in curr:
9
                curr.remove(s[left])
10
                left += 1
11
            curr.add(ch)
12
            ans = max(right - left + 1 , ans)
13

14
        return ans

1
from src.python._003_Longest_Substring_Without_Repeating_Characters import Solution
2

3

4
sol = Solution()
5

6
assert sol.lengthOfLongestSubstring("abcabcbb") == 3
7
assert sol.lengthOfLongestSubstring("bbbbb") == 1
8
assert sol.lengthOfLongestSubstring("pwwkew") == 3
9
assert sol.lengthOfLongestSubstring("") == 0
10
assert sol.lengthOfLongestSubstring(" ") == 1
11
assert sol.lengthOfLongestSubstring("abba") == 2
12

13
print("PASS")

参考资料#

• LeetCode 原题：https://leetcode.com/problems/longest-substring-without-repeating-characters/
• 力扣题解页：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/