[Leetcode 3] 无重复字符的最长子串

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
示例 2:
示例 3:
notion image
说明:
  • 0 <= s.length <= 5 * 10000
  • s 由英文字母、数字、符号和空格组成
 

解法一:滑动窗口 + Set

[l, r] 是当前无重复的窗口。右指针 r 每次尝试加入新字符
  • 如果 ch 没在窗口里,它就能被安全地加入窗口,长度更新;
  • 如果 ch 已经在窗口里,说明窗口里出现了重复。左指针 l 右移,从左边一点点收,同时把滑出窗口的字符从 set 里移除,直到集合中没有字符与 ch 冲突。
集合始终是窗口内的字符集,窗口内永远保持“无重复”。
复杂度:
  • 时间:O(N)(每个字符最多进/出集合各一次)
  • 空间:O(min(N, |Σ|))(Σ 为字符集合;集合最多装下当前窗口大小)

解法二:滑动窗口 + 哈希(推荐)

上一种解法在遇到冲突时,一步步收缩左端。
其实我们可以“跳着走”:维护一个哈希last[c] 记录字符 c 上次出现的下一个位置(即 last[c] = 上次出现的索引 + 1)。
当右指针 r 看到了字符 ch
  • 如果 ch 没出现过,那就正常更新长度;
  • 如果 ch 出现过,意味着当前窗口 [l, r] 里包含了旧的 ch,那左端至少要跳到 last[ch] 才能避开,于是 l = max(l, last[ch]) 直接跳过重复段。其中max 很关键,避免左端倒退
复杂度:
  • 时间:O(N)(每个位置访问/更新一次字典)
  • 空间:O(min(N, |Σ|))(字典最多记录每个字符的最近位置)
上一篇
Understanding Recursion: Functions That Call Themselves
下一篇
[Leetcode 4] 两个排序数组的中位数