leetcode_3_无重复字符的最长子串

无重复字符的最长子串

描述

中等

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

示例：

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

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

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

解题

遍历s并借助字典记录下不同字符出现位置

当遍历到一个字符，且该字符出现在字典中时，说明出现了重复字符

此时，这两个重复字符之间的距离就是无重复字符的长度

设置左右指针left和right（滑动窗口）

当left和right之间没有重复字符时，无重复最大子串长度为right-left

当出现重复时，向右移动left指针，保证left和right之间无重复元素

当有重复元素出现时

if s[right] in dic:
    left = max(dic[s[right]], left)

更新left并不是直接等于上一个重复元素的位置

例如"abcba"

当右指针扫描到第二个"b"时，left更新为指向第一个"b"

当右指针扫描到第二个"a"时，需要判断，left是否需要更新

代码中使用max就解决了这个问题

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        left = -1  # 初始位置长度，用于记录上一个重复字符的位置
        res = 0
        for right in range(len(s)):
            # 当出现重复元素时，更新left
            if s[right] in dic:
                left = max(dic[s[right]], left)
            res = max(res, right - left)
            dic[s[right]] = right  # 添加/更新字符位置

        return res

或者更直观的窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        left = 0
        res = 0		# 保存最大的长度
        cur = 0 	# 当前窗口的长度
        for right in range(len(s)):
            cur += 1
            # 从左往右删除元素，直到窗口中没有重复字符
            while s[right] in window:
                window.remove(s[left])
                left += 1
                cur -= 1
            res = max(res, cur)
            window.add(s[right])
        return res