3. 无重复字符的最长子串

发表于 更新于 分类于

1. 简介

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

2. 题解

这题可以用双指针来做，这里以查找字符串 "abcbb" 为例，查看一下大致的流程

一开始，我们初始化最大长度、当前结果和当前长度、左右指针。当前结果用集合来存放，帮助我们快速判断是否存在重复字符

首先，左右指针均指向第一个字符，当前结果为 "a"，其长度大于最大长度 0，更新最大长度为 1

右指针往右搜索，此时指向字符 "b"，字符 "b" 不在当前结果中，故当前结果为 "ab"，更新最大长度为 2

右指针继续搜索，"c" 同样没有重复，更新最大长度为 3

右指针再往右时指向了字符 "b"，而 "b" 是一个重复字符，这时需要让左指针往右移动，直到当前子串中没有重复字符

左指针指向下一个字符，此时子串为 "bcb"，仍有重复字符 "b"，左指针还需要继续往右移动

此时子串为 "cb"，没有重复字符，但是长度为 2，不更新最大长度

右指针往右，此时子串为 "cbb"，出现重复字符 "b"，右移左指针

左指针不断右移，直到子串没有重复的字符，在我们的例子中，这时 left=right=4，子串为 "b"，不更新最大长度。

此时已经遍历完整个字符串，输出我们记录的最大长度即可。

如果用文字表示上图的流程，大致为：

  • 初始化所需的变量；
  • 遍历字符串 s 中的每个字符；
    • 如果 left 和 right 截取的子串没有重复的字符，更新当前的子串，如果当前子串长度大于最大长度，则更新最大长度；
    • 如果 right 指向的字符出现了重复，则 left 往右增长，直到当前子串中没有重复的字符，更新当前子串，如果当前子串的长度大于最大长度，则更新最大长度。
  • 返回最大长度。

根据上述流程，实现的 python 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len, cur_len = 0, 0
        left = right = 0
        lookup = set()
        for right in range(len(s)):
            while s[right] in lookup:
                lookup.remove(s[left])
                left += 1
                continue
            lookup.add(s[right])
            cur_len = len(lookup)
            if cur_len > max_len:
                max_len = cur_len
        return max_len