3. 无重复字符的最长子串

题目描述

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

思路

可以用滑动窗口实现：

• 用一个右指针遍历字符；
• 一个左指针作为范围起点，用哈希表（哈希集合）存当前范围内出现的字符；
• 用一个变量记录最长的子串长度；
• 每次右指针循环一个字符时，判断这个字符是否在集合中出现，如果出现了则：
  • 从左向右抛出字符；
  • 更新当前子串长度；
  • 更新左指针位置；
• 在判断字符出现后，进行：
  • 最后添加当前字符；
  • 更新最长子串长度。

最终代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        cur_s = set()
        cur_l = 0
        l = 0
        for ch in s:
            if ch in cur_s:
                while ch in cur_s:
                    cur_s.remove(s[l])
                    cur_l -= 1
                    l += 1
            cur_s.add(ch)
            cur_l += 1
            max_len = max(cur_l, max_len)
        return max_len

看了一下别人的代码，有更简洁的更新方式：每次在遍历时通过切片判断是否存在该字符。然后直接更新下标：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l,r = 0, 0
        max_len = 0
        while r < len(s):
            if s[r] in s[l:r]:
                l+=1
                continue
            max_len = max(max_len, r-l+1)
            r+=1
        return max_len