3. 无重复字符的最长子串¶
题目¶
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题解¶
Go
func lengthOfLongestSubstring(s string) (ans int) {
window := [128]bool{} // 也可以用 map，这里为了效率用的数组
left := 0
for right, c := range s {
// 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
// 所以要在加入 c 之前，先移出窗口内的 c
for window[c] { // 窗口内有 c
window[s[left]] = false
left++ // 缩小窗口
}
window[c] = true // 加入 c
ans = max(ans, right - left + 1) // 更新窗口长度最大值
}
return
}
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans, left = 0, 0
window = set()
for idx, c in enumerate(s):
while c in window: # 窗口中已经出现过字符c
window.remove(s[left])
left += 1
window.add(c)
ans = max(ans, idx - left + 1)
return ans
复杂度¶
- 时间复杂度: \(O(n)\)，其中 \(n\) 是 \(s\) 的长度。
- 空间复杂度: \(O(|\Sigma|)\)，其中\(|\Sigma|\)为字符集合的大小，本题中字符均为 ASCII 字符，所以 \(|\Sigma| \leq 128\)。