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

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

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

• 思路

  1. 滑动窗口法

     • 窗口代表当前考虑的子串

     • 左边界和右边界可以动态调整

  2. 数据结构选择

     • 需要一个高效的方式来判断字符是否重复

     • 考虑使用集合或哈希表来存储窗口内的字符

  3. 窗口扩张与收缩

     • 右指针通常用于扩展窗口（探索新字符）

     • 当发现重复时，左指针用于收缩窗口（排除重复字符）

  4. 记录最大值

     • 在每次窗口调整后，记录当前最大长度

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""recent = set() # 创建一个集合来存储当前窗口的字符left = 0max_len = 0for right in range(len(s)):while s[right] in recent: # 如果当前字符已经在set中，移动left指针，直到无重复 (一定是先判断当前字符在不在set中,否则会将重复的字符添加到set中)recent.remove(s[left]) left += 1recent.add(s[right])max_len = max(max_len, right - left + 1) # 更新当前最大无重复子串的长度return max_len

• 时间复杂度：O(n) （每个字符最多被访问两次，左指针和右指针各一次）
• 空间复杂度：O(min(m, n)) （m 是字符集大小，n 是字符串长度）