[3][中等][滑动窗口] 无重复字符的最长子串

题目描述

3. 无重复字符的最长子串 剑指 Offer 48. 最长不含重复字符的子字符串

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

我的思路

1. 首先使用一个滑动窗口, 或者是双指针, 始终指示着当前最长的无重复子串的开始和结尾

2. 对当前的字符(还未判断)进行判断, 是否能够使目前的无重复子串长度+1

   • 比较快的判断方法, 就是把目前无重复子串中的每一个字符加入到一个集合(set)当中, 就能用$O(1)$的时间进行判断了

   • 如果当前字符不在集合中, 那么无重复子串可以延长, 并把这个字符加入到集合中

3. 如果当前字符在集合中, 无重复子串中已经包含了这个字符, 则不能延长, 需要考虑抛弃子串中的部分内容, 抛弃的内容即为子串的第一个字符到这个重复的字符(包含). 因此需要有一个指针一直指向子串的第一个字符, 然后滑动抛弃.

这样的时间复杂度为$O(n)$, $n$为字符串的长度.

对应的代码为:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        temp_set, max_len = set(), 0
        start = 0
        for i in range(n):
            if s[i] not in temp_set:
                temp_set.add(s[i])
                if len(temp_set) > max_len:
                    max_len = len(temp_set)
            else:
                while s[start] != s[i]:
                    temp_set.remove(s[start])
                    start += 1
                start += 1

        return max_len