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

Author：baiyucraft

BLog： baiyucraft’s Home

一、题目描述

题目地址：3. 无重复字符的最长子串

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

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: s = “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

输入: s = “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

输入: s = “”

输出: 0

二、思路以及代码

  此题一般最无脑的做法肯定是暴力解法，即遍历每个字符串，找出以该字符开头，不包含重复字符的最长子串。所以在解题前，我们先用abcabcbb这个字符串来模拟暴力解法搜索无重复字符的最长子串的过程：

  可以发现一点，如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的，原理其实很简单，当我们枚举第i个字符开头的子串时，长度为k的子串不重复，长度为k+1的子串重复，即s的i ->i+k子串中无重复元素，那显然 i+1 ->i+k子串中也无重复元素，并且我们可以继续尝试增大该子串，直到子串中出现了重复元素。这样一来就有了滑动窗口这一概念。

1.滑动窗口

思路： 我们使用左右指针left和right来确定滑动窗口的边界。在之后的的操作中，左指针向右移动一格，右指针保证左右指针范围内的是无重复字符的最大子串我，并用max_len记录下这个子串的长度。其中用集合set类型的ooc来存储判断子串中的字符是否重复。

动画：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # occ记录子串中的字符是否重复
        occ = set()
        # n为字符串s的长度
        n = len(s)
        # right为右边界，最大长度max_len初值为0
        right, max_len = -1, 0
        # left左边界开始枚举
        for left in range(n):
            # 除了第一次，左指针向右移动一格，移除一个字符
            if left != 0:
                occ.remove(s[left - 1]) 
            # 不断地移动右指针
            while right + 1 < n and s[right + 1] not in occ:
                occ.add(s[right + 1])
                right += 1
            # 第 left 到 right 个字符是一个无重复字符子串
            max_len = max(max_len, right - left + 1)
        return max_len

复杂度分析：

时间复杂度：o(n)o(n)

空间复杂度：o(∣Σ∣)o(\left| \Sigma \right|)，Σ\Sigma为字符集大小

2.滑动窗口-优化

思路： 在上文中，我们会发现滑动的过程中left要枚举s中的每一个数，并且right也要枚举s中的每一个数，那么有什么办法能优化窗口呢？

 我们想到用右边界right来枚举字符串中的每一个字符，用名为c_dic的字典来存储字符的同时，存储该字符离right最近的下标。

 left左侧边界初值为0，每次枚举right向右移动一格时：

  • 如果该字符在c_dic中，说明是个重复字符，这时：
    • 若left小于等于该字符上一次出现的下标，说明该窗口中的子串重复，则将left替换为该字符上一次出现的下标的后一个位置，并且将该字符下标更新为right
    • 若left大于该字符上一次出现的下标，则继续以left为左边界来枚举
  • 如果该字符不在c_dic中，则存入并记录该次枚举后right - left + 1的值并与max_len比较替换

动画：

LeetCode-3-3

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        c_dic = {}
        # 左边界left初值为0，max_len初值为0
        left, max_len = 0, 0
        for right, c in enumerate(s):
            # 如果c在字典中 并且 左边界left小于等于该字符上一次出现的下标（重复）
            if c in c_dic and left <= c_dic[c]:
                # 将left替换为该字符上一次出现的下标的后一个位置
                left = c_dic[c] + 1
                # 将该字符下标更新为right
                c_dic[c] = right
            else:
                # 存入字典
                c_dic[c] = right
                # 计算长度
                max_len = max(max_len, right - left + 1)
        return max_len

复杂度分析：

时间复杂度：o(n)o(n)

空间复杂度：o(∣Σ∣)o(\left| \Sigma \right|)，Σ\Sigma为字符集大小

LeetCode
#Python #LeetCode #字符串
LeetCode题解 3. 无重复字符的最长子串
http://baiyucraft.top/LeetCode/LeetCode-3.html
作者
baiyucraft
发布于
2021年5月22日
许可协议