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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。


思路讲解-滑动窗口

假设原始字符串S如下



从左侧开始遍历S,以i标记窗口左侧,j标记窗口右侧,初始时,i=0,j=0,即开头a所在的位置,此时,窗口大小为1

然后,将j右移,逐步扩大窗口,依次经过b、c、d,此时,窗口内均无重复字符,继续右移j



当j移动到d后面的a所在位置时,对应字符a在窗口中已存在,此时,窗口大小为5,去除当前重复的一位,窗口大小为4。此时窗口内的字符串abcd为



找到窗口中已存在的该字符所在位置,并将i移动到该位置下一位



此时为第二个窗口



继续重复之前的操作,直到j移动到字符串最后一位停止。
代码示例:

class Solution:
def lengthOfLongestSubstring(self, s: str): # -> int:
i = 0
j = 1
max = 0

while j <= len(s):
subs = s[i:j] # 字串
# 如果存在重复的,i后移一位
if len(set(subs)) != len(subs):
i += 1
# 不存在重复的则j后移一位
else:
j += 1
if len(subs) > max:
max = len(subs)
return max


声明:此资源由空瓶网 [kongping.net] 收集整理于网络,仅供学习交流!请于下载24小时内删除!如有侵权请联系空瓶网 [yiouejv@126.com] 删除处理。
分享到
  • 微信好友
  • QQ好友
  • QQ空间
  • 百度贴吧
  • 新浪微博
  • 复制网址
上一篇
热门帖子:
相关阅读:

你肿么看?

#免责声明# 广告合作 网站地图 空瓶网©2018-2019 (kongping.net) 冀ICP备17031746号
所有视频资源和下载地址均来自于第三方网站,并不提供影片资源存储,仅供测试和学习交流。如果有侵犯版权的资源请发送邮箱至yiouejv@126.com,我们会在24小时之内处理!