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

示例 1：

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

示例 2：

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

示例 3：

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

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_n = 0
        l = []
        for v in s:
            if v in l:
                while v in l:
                    l.pop(0)
            l.append(v)

            max_n = max(max_n, len(l))

        return max_n

• 核心思路：遍历字符串，并维护一段“当前不含重复字符”的连续子串 l，同时记录最大子串长度
• 时间复杂度最坏情况 $O(n^2)$
• 空间复杂度最坏情况 $O(n)$
• max_n 存储当前最长子串的长度
• l 存储当前处理中的子串