题目描述

[EN | CN]

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

示例 1:

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

示例 2:

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

示例 3:

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

解法 1:滑动窗口

这里先明确一下两个概念:

  • 「子序列」是 subsequence,指的是原字符串中的按顺序的子集,例如「abc」可以是「a1b2c」的子序列。
  • 「子串」是 substring,指的是原字符串中切出来的连续字符串,而「abc」不是「a1b2c」的子串。

这道题肯定不能暴力解。很容易想到利用一个可变长的滑动窗口(可以用两个索引 startend 来表示),该窗口的右侧不断往前滑动(end++),如果遇到窗口中已有的重复字符(即索引在 startend 之间)则将 start 跳到该字符的后一个位置。元素的索引可以用一个 dict 来保存字符最后出现的索引。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,总是要遍历一遍;
  • 空间复杂度为 $O(n)$,需要存储每个值的索引。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_to_idx = dict()
        start, max_ = 0, 0

        for end, end_val in enumerate(s):
            if end_val in char_to_idx and char_to_idx[end_val] >= start:
                start = char_to_idx[end_val] + 1
            else:
                max_ = max(max_, end - start + 1)
            char_to_idx[end_val] = end

        return max_
  • 执行用时 :64 ms, 在所有 Python3 提交中击败了85.78%的用户。
  • 内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.03%的用户。