1. 题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
2. 解题思路
2.1 朴素解法,暴力搜索
为了枚举给定字符串的所有子字符串,我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 和 。那么我们有 ,(这里的结束索引 j 是按惯例排除的)。因此,使用 从0到n - 1,n−1 以及 j 从 i+1 到 n 这两个嵌套的循环,我们可以枚举出 s 的所有子字符串。
要检查一个字符串是否有重复字符,我们可以使用集合。我们遍历字符串中的所有字符,并将它们逐个放入 set 中。在放置一个字符之前,我们检查该集合是否已经包含它。如果包含,我们会返回 false。循环结束后,我们返回 true。
2.2 滑动窗口
利用python 的字典,或者java中的Map<Character, Integer> map
存储每个字符出现位置的索引。
使用变量end来记录上次该字符出现的位置长度,删掉从该字符前一次出现,及其以前的重复出现,也可以理解成不重复字符串的开始位置;
使用变量m来记录不重复字符出现的最大长度;
each是遍历字符串的当前index
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0 : return 0
end = 0
dic = {}
m = 0
for each in range(len(s)):
if s[each] in dic :
end = max(end,dic[s[each]]+1)
dic[s[each]] = each
m = max(m,each-end+1)
return m
第二种理解思路:
求无重复字符的最长子串的长度,从头到尾遍历字符串时(索引index),考虑到无重复字符,我们先把字符逐个放到容器set中,并更新最长子串的长度,如果遇到了重复字符,即当前遍历的字符在set中,则要从set中删除重复字符,包括这个重复字符前面的所有字符,也就是从当前子串的最左边(left)开始删除,直到删除重复字符
3. 总结/分类
字符串,滑动窗口