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

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

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

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

提示：
s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解题思路

方法一：滑动窗口+set
使用遍历，从每个位置建立一个set，挨个往set里面加后面的字符，如果加了以后发现len(set)没有变大，说明碰见重复字符了，记录下当前无重复子串的长度new_length。遍历完整个字符串， max(new_length, result)就是我们想要的结果。
时间复杂度为O(n²)。
方法二：双指针+dic索引
我们可以使用哈希表记录每个字符的下一个索引，然后尽量向右移动尾指针来拓展窗口，并更新窗口的最大长度。如果尾指针指向的元素重复，则将头指针直接移动到窗口中重复元素的右侧。
定义tail为当前遍历到的那个字符，head为“符合条件的子串的开头位置”。
可以看出，如果tail之前的字符a曾经在之前出现过，而且之前出现过的位置之后没有出现别的字符（如b，c等）重复的状况，就需要把head更新为上次a出现的位置。

操作视频见https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/
时间复杂度为O(n)。

解题代码

方法一：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            check_set = set()
            for j in range(i, len(s)):
                old_length = len(check_set)
                check_set.add(s[j])
                new_length = len(check_set)
                result = max(new_length, result)
                if old_length == new_length:
                    break
        return result

方法二：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        head, tail = -1, 0  # -1是为了s为单个字符时，结果能输出1
        check_map = {}  # 某字符：字符出现的首个位置
        for tail in range(len(s)):
            if s[tail] in check_map:
                head = max(check_map[s[tail]], head) # 注意这里是不是head = check_map[tail]，假设此时有"tmmzuxt"，则遍历到最后一个t的时候，希望的head是【第一个m】的位置1
            check_map[s[tail]] = tail
            result = max(result, tail - head)
        return result

为什么要用head = max(check_map[s[tail]], head)而不是head = check_map[s[tail]]？
因为slow不能回溯，如果输入为[3, 3, 2, 1, 3, 3, 3, 1]的话，每次循环输出的head和tail分别为：
-1 0
0 1
0 2
0 3
1 4
4 5
5 6
5 7
以及
-1 0
0 1
0 2
0 3
1 4
4 5
5 6
3 7
可以看到第二种方式，因为前面有元素1，导致了head的回溯。而此时前面的1后面的字符串已经比较过了，回溯会导致tail - head瞬间变大，造成结果错误。

执行结果

方法一：执行用时: 876 ms 内存消耗: 15 MB
方法二：执行用时：56 ms 内存消耗：15.1 MB