def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# left是不重复序列的开头
# 保留一个map记录不重复序列元素的index
# 遍历序列,记录元素的index到map中
# 当遇到之前已经出现的元素,新获得一个不重复序列长度为当前index和
# 当前元素在前一次出现的index之差
# 更新left 和 map:
# 把 left 到 当前元素在前一次出现的index 之间的元素 剔除出map
# 更新left为 当前元素在前一次出现的index +1
# 最后一个不重复数组是数组长度-最后更新的left,再做一次判断
if not s:
return 0
res = 0
left = 0
sdic = {s[0]:0}
for i in range(1, len(s)):
if s[i] in sdic.keys():
res = max(res, i - left)
cur_pre = sdic[s[i]]
for j in range(left, cur_pre + 1):
sdic.pop(s[j])
left = cur_pre + 1
sdic[s[i]] = i
res = max(res, len(s) - left)
return res
3. 最长不重复子序列
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 作者：寒小阳 时间：2013年9月。出处：http://blog.csdn.net/han_xiaoyang/ar...
- 描述 给出一个字符串，找到最长的重复子序列的长度，并且这两个子序列不能在相同位置有同一元素。比如：在两个子序列中的...
